Description

Mingming has $n$ very beautiful beads and several strings of different colors. Now Mingming wants to use strings to connect all the beads into a whole.

It is known that all beads are distinct and are numbered from $1$ to $n$. For bead $i$ and bead $j$, you may choose not to connect them, or choose one string from $c_{i,j}$ strings of different colors to connect them. If we view beads as vertices and strings as edges, connecting all beads into a whole means that all vertices form a connected graph. In particular, a bead cannot be connected to itself.

Mingming wants to know how many different ways there are to connect all the beads into a whole. Since the answer may be very large, output the result modulo $1000000007$.

Input Format

The first line contains a positive integer $n$, the number of beads. The next $n$ lines each contain $n$ non-negative integers separated by spaces. In these $n$ lines, the $j$-th number in the $i$-th line is $c_{i,j}$.

Output Format

Output one integer in one line, the number of connection schemes modulo $1000000007$.

3
0 2 3
2 0 4
3 4 0

50

Hint

Sample Explanation

Depending on whether each pair of beads is connected, there are the following four types of connection methods.

For each type, the number of methods it contains is the product of the $c_{i,j}$ values of the corresponding included edges.

Graph (1) has $2\times3\times4=24$ methods, graph (2) has $2\times4=8$ methods, graph (3) has $2\times3=6$ methods, and graph (4) has $3\times4=12$ methods, for a total of $50$ methods.

Constraints

For $100\%$ of the testdata, $n$ is a positive integer, and all $c_{i,j}$ are non-negative integers not exceeding $1000000007$. It is guaranteed that $c_{i,j}=c_{j,i}$. The values of $n$ for each test group are as follows.

Translated by ChatGPT 5