Counting Connected Bead Graphs

Given n distinct beads numbered from 1 to n and a rope set between every pair of beads, you are to count the number of ways to connect all beads into one connected configuration. For every pair of beads i and j (with i ≠ j), you can either choose not to connect them or choose one rope out of \( c_{i,j} \) ropes (each rope has a distinct color) to connect them. A configuration is valid if the graph (with beads as nodes and selected ropes as edges) is connected. Since the answer can be huge, output it modulo \(10^9+7\).

Note: The rope count \( c_{i,j} \) is given for every pair \( (i,j) \) (with 1-based indices). Although an edge is available between each pair, you may opt not to use it. Self-loops are not allowed.

The total number of ways to choose rope options on all pairs (without connectivity restrictions) is \[ \prod_{1 \le i < j \le n} (1+c_{i,j}). \] A configuration is valid if the graph is connected. One effective method to explicitly count the connected cases is by using the inclusion–exclusion principle on subsets of beads.

inputFormat

The first line contains a single integer \( n \) representing the number of beads. The next \( n \) lines each contain \( n \) space‐separated integers. The \( j^{th} \) integer in the \( i^{th} \) line is \( c_{i,j} \) (for \(1 \le i, j \le n\)). It is guaranteed that \( c_{i,i} \) is not used and the beads are numbered from 1 to \( n \).

outputFormat

Output a single integer: the number of ways to connect all beads so that the graph is connected, modulo \(10^9+7\).

sample

2
0 1
1 0

1