{"raw_statement":[{"iden":"problem statement","content":"We have a graph with $N$ vertices numbered $1, 2, \\dots, N$. Initially, it has no edges.  \nNow, let us add some number of undirected edges to $G$ so that the following condition holds for any $i, j\\,(i ≠ j)$ after addition.\n\n*   If $A_{i, j} = 1$, there is an edge directly connecting Vertex $i$ and Vertex $j$;\n*   if $A_{i, j} = 0$, there is no edge directly connecting Vertex $i$ and Vertex $j$;\n*   if $A_{i, j} = -1$, either is fine.\n\nAmong the graphs that can be $G$ after addition, how many are trees?  \nSince the count can be enormous, find it modulo $(10^9 + 7)$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 ≤ N ≤ 300$\n*   $-1 ≤ A_{i, j} = A_{j, i} ≤ 1$\n*   $A_{i, i} = 0$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_{1, 1}$ $\\cdots$ $A_{1, N}$\n$\\vdots$\n$A_{N, 1}$ $\\cdots$ $A_{N, N}$"},{"iden":"sample input 1","content":"4\n0 1 -1 0\n1 0 -1 -1\n-1 -1 0 0\n0 -1 0 0"},{"iden":"sample output 1","content":"2\n\nWe need an edge between Vertex $1$ and Vertex $2$, and we must not add an edge between Vertex $1$ and Vertex $4$ or between Vertex $3$ and Vertex $4$.\nThus, we have the following two valid graphs:\n![image](https://img.atcoder.jp/ghi/0f55bf9e7a13aef4bddde12f87a23d5d.png)"},{"iden":"sample input 2","content":"3\n0 1 1\n1 0 1\n1 1 0"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"3\n0 0 0\n0 0 0\n0 0 0"},{"iden":"sample output 3","content":"0"},{"iden":"sample input 4","content":"11\n0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n-1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1\n-1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1\n-1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1\n-1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1\n-1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1\n-1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1\n-1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1\n-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1\n-1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1\n-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0"},{"iden":"sample output 4","content":"357947677\n\nWhen we distinguish the vertices, there are $11^9$ trees with $11$ vertices."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}