TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

JOI 君最喜歡圖了,他生日的時候收到了一張一般有向圖,覺得實在很一般,所以就想要在上面數有趣的東西。
他很想知道這張圖上有多少條簡單路徑。
一條簡單路徑就是從一個點經過一些邊走到另外一個點(可以完全不經過邊),過程經過的所有點(包含起終點)全部都不重複。
請你幫幫 JOI 君。

注意到因為方案數可能太大了,所以 JOI 君只在意方案數取 109+7 的餘數。
也就是說,如果方案數為 T,請輸出 T(mod109+7)

Input Format

輸入第一行有一個正整數 N(N20) 代表這張圖有幾個節點。
接下來 N 行,每行都有 N 個整數由一個空白隔開,第 i 行第 j 個數字代表 Ai,j。其中 Ai,j{0,1}
如果第 i 個節點往第 j 個節點有一題邊,則 Ai,j=1
否則 Ai,j=0

Output Format

輸出一行一個整數代表答案。

Sample Input 1

2
0 1
1 0

Sample Output 1

4

Sample Input 2

2
0 0
0 0

Sample Output 2

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2