Some Hamiltonian paths

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$ .

Problem information

Author: Unknown
Translator: Salvador Roura

Generation: 2026-01-25T11:50:24.126Z