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?

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.

提交代码