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 \times 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 \ge 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 \to y$ and $y \to z$ are both painted. The test cases are such that the answer is smaller than $10^6$.