Some Hamiltonian paths P90225

Consider a directed graph with n vertices and all the n(n − 1) possible arcs, some of which are painted. How many Hamiltonian paths are in the graph starting at vertex 0, ending at vertex n−1, and such that they do not traverse two consecutive painted arcs?

Input

Input consists of several cases. Every case begins with n, followed by an n × n matrix, where the position (i, j) has the color of the arc from vertex i to vertex j. A one indicates a painted arc, and a zero a non-painted arc. The diagonal (which is useless) only has zeroes. You can assume n ≥ 2.

Output

For every case, print the number of permutations of the n vertices that start at 0, end at n − 1, and do not have three consecutive vertices x, y and z such that the two arcs x → y and y → z are both painted. The test cases are such that the answer is smaller than 10⁶.