## 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

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.

### Output

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

### Example

Input:2 00 00 2 01 10 0Output:0 2

Added by: | Fudan University Problem Setters |

Date: | 2009-05-23 |

Time limit: | 2s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | Fudan University Local Contest #1 |