# Some Hamiltonian paths P90225

Statement

html

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 xy and yz are both painted. The test cases are such that the answer is smaller than 106.

Public test cases
• Input

```2
0 1
1 0

3
0 1 1
1 0 0
1 1 0

3
0 1 0
0 0 1
0 0 0

5
0 1 0 0 0
1 0 1 0 0
0 0 0 0 1
1 0 0 0 1
0 1 0 0 0
```

Output

```1
1
0
4
```
• Information
Author