Optional Array Permutation

Time Limit: 2000ms

Memory Limit: 65535Kb

Description

There is an array which consists of a set of n numbers (1..n, respectively). Differing from original meaning of array permutation, this problem contains several constraints restricting some permutation from being legal. Every constraint is a vector composed by a pair of integers A and B, saying that the A are supposed to be ahead of B. For example, as for one of the permutation 2 1 3 4 in the case of n=4, it satisfies the constraint (2,1) (2,3) (2,4), while it doesn't satisfy(3,2)(3,1),(3,4) etc. So much so that, how much is number of different legal permutations that satisfy all of the given constraint?

Input

There are several test cases.

For each test case, the first line contains one positive integer n (n<=16) as the information said above. The following contains n lines, each of which containsn integers, the element at ith row and jth column is either 1 or 0. Legal permutation should satisfy the constraint (i, j) if and only if the value ofthe element is 1. You can assume that any pair of (i, j) is bound to be 0 if i is equal to j.

The input ends with EOF.

Output

For each test case, output the number of different legal permutations mod 10007.

Sample Input

2
0 1
1 0
3
0 0 0
0 0 0
0 0 0
3
0 0 0
1 0 0
0 1 0
3
0 0 0
0 0 1
0 0 0

Sample Output

0
6
1
3

Hint

None

Source

崔嵬

提交代码