VMCOUNT - Pirate đi thực tập

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Hè này, Pirate đã rời đảo dừa để bắt đầu bước vào đời với một công việc thực tập ở một công ty lớn. Tuy nhiên thì vạn sự khởi đầu nan giải, sếp của Pirate đã giao cho anh một công việc vô cùng khó khăn:

Cho một đồ thị đơn có hướng, đếm xem có bao nhiêu đường đi Hamilton giữa 2 đỉnh bất kỳ của đồ thị.

Cầm ma trận kề của đồ thị trong tay mà lòng Pirate chỉ muốn khóc. Sau nhiều ngày suy nghĩ quên cả ăn uống tắm rửa, Pirate đã quyết định viết một chương trình để đếm. Tiếc là do dạo này đi thực tập quá nhiều, chỉ toàn ngồi đọc code, khả năng code đã dần không còn nữa. Các bạn có thể giúp Pirate không? Tất nhiên để giúp đỡ các bạn, Pirate sẵn sàng đưa tận tay các bạn mô tả chi tiết của các đồ thị (dù đấy là bí mật công ty).

Chú thích : Đường đi trên đồ thị là một dãy các đỉnh mà hai đỉnh liên tiếp đều có cạnh nối với nhau. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ được đi qua một lần.

Yêu cầu

Đây là bài toán Output-Only, tức là các bạn sẽ được download về một tập các input. Sau đó, chỉ cần nộp file output (không cần nộp chương trình).

Input

Bạn được cho 10 file input ở đây . Mỗi file input gồm:

  • Dòng 1: số nguyên N, số đỉnh của đồ thị.
  • N dòng tiếp, mỗi dòng gồm đúng N ký tự 0 hoặc 1. Ký tự j ở dòng i bằng 0 nếu không có cạnh (i,j), và bằng 1 nếu có cạnh (i,j). Các đỉnh của đồ thị được đánh số từ 1 đến N.

Output

Gồm đúng 10 dòng, mỗi dòng in ra một số nguyên duy nhất là kết quả của bài toán, theo module 109 + 7 (1000000007).

Chú ý: Bạn nên output đủ 10 dòng. Những input không trả lời được bạn nên output ra số 0.

    Chấm điểm

    Bài của bạn sẽ được chấm trên thang điểm 100.

    Trong quá trình thi, chỉ output 1 của bạn được chấm (nghĩa là bạn chỉ có thể được 0 hoặc 100 điểm, tương ứng với việc dòng 1 của output sai hay đúng).

    Sau khi vòng thi kết thúc, cả 10 output của bạn sẽ được chấm, bạn sẽ nhận được 10 điểm với mỗi output đúng.

    Example

    Input:
    3
    011
    101
    110
    Output:
    6
    


    • Người up: voj
    • Nguồn bài: VM13 - Nguyễn Xuân Khánh