Alguns camins Hamiltonians P90225

Suposeu un graf dirigit amb $n$ vèrtexs i tots els $n(n - 1)$ arcs possibles, alguns dels quals estan pintats. Quant camins Hamiltonians hi ha que comencin en el vèrtex 0, acabin en el vèrtex $n-1$, i no passin per dos arcs pintats consecutius?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, seguit d’una matriu $n \times n$ on a la posició $(i, j)$ hi ha el color de l’arc que va del vèrtex $i$ fins al $j$. Un u indica que l’arc està pintat, i un zero que no. La diagonal (que és inútil) només té zeros. Suposeu $n \ge 2$.

Sortida

Per a cada cas, escriviu quantes permutacions dels $n$ vèrtexs comencen en 0, acaben en $n - 1$, i no tenen tres vèrtexs consecutius $x$, $y$ i $z$ tals que els dos arcs $x \to y$ i $y \to z$ estiguin pintats. Els jocs de proves són tals que la resposta és més petita que $10^6$.