{"problem":{"name":"Spanning Tree","description":{"content":"We have a graph with $N$ vertices numbered $1, 2, \\dots, N$. Initially, it has no edges.   Now, let us add some number of undirected edges to $G$ so that the following condition holds for any $i, j\\,(","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"jsc2021_g"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 ≤ N ≤ 300$\n*   $-1 ≤ A_{i, j} = A_{j, i} ≤ 1$\n*   $A_{i, i} = 0$\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"jsc2021_g","tags":[],"sample_group":[["4\n0 1 -1 0\n1 0 -1 -1\n-1 -1 0 0\n0 -1 0 0","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)"],["3\n0 1 1\n1 0 1\n1 1 0","0"],["3\n0 0 0\n0 0 0\n0 0 0","0"],["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","357947677\n\nWhen we distinguish the vertices, there are $11^9$ trees with $11$ vertices."]],"created_at":"2026-03-03 11:01:14"}}