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^{6}.

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
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++