SP4407 DAGCNT - Counting Arborescence

_"In graph theory, an arborescence is a directed graph in which, for a vertex v called the root and any other vertex u, there is exactly one directed path from v to u. In other words, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph."_ \-- from Wikipedia, the free encyclopedia You are given a directed graph with _N_ vertices, and your task is to count the number of different arborescences of size _N_ that can be found in the given graph. Two arborescences are considered different when they consist of different edges.

Input consists of multiple test cases. For each test case, the first line contains one integer _N_ described as above. N lines follows, each consists of _N_ characters, either '0' or '1', representing the adjacency matrix of the graph. The directed graph contains edge (_i_,_j_) if and only if the _j_th character of the _i_th line of the matrix is '1'. The graph consists of no more than 8 vertices. End of input is indicated by a line consisting of a single 0.

For each test case, output one line consisting of one single integer, the number of arborescences.