Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMCOUNT - Pirate đi thực tập

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

Được gửi lên bởi:VOJ Team
Ngày:2013-05-28
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:TEXT
Nguồn bài:VM13 - Nguyễn Xuân Khánh

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.