题目描述

You found a complete, undirected graph with $n$ nodes, labeled $1..n$. Each edge has a color. For simplicity, each color is identified by a number between 1 and 300 inclusive. Interestingly, you noticed that for each and every simple cycle in this graph, there are two adjacent edges on this cycle which have the same color.

For each non-empty subset of nodes in graph $S$, let $f(S)$ denote the size of the maximum subset of nodes you can choose from $S$ such that all edges between the chosen nodes are the same color. Compute the sum of $f(S)$ over all non empty subsets $S$ of nodes in the graph.

输入格式

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($1 \leq n \leq 300$), which is the number of nodes in the graph.

The next $n$ lines will each contain $n$ integers $c$ ($0 \leq c \leq 300$), which is a matrix representing the colors of the edges, where $c[x, y]$ is the color of the edge between node $x$ and node $y$. It is guaranteed that the values on the diagonal will be 0 ($c[x, x] = 0$), since there is no edge from a node to itself. It is also guaranteed that the matrix is symmetric and the off-diagonal colors range from 1 to 300 ($1 \leq c[x, y] = c[y, x] \leq 300$ for $x \neq y$).

输出格式

Output a single integer, which is the sum of $f(S)$ over all non empty subsets $S$ of nodes in the graph. Since this number may be very large, output it modulo $10^9 + 7$.

4
0 1 1 1
1 0 2 2
1 2 0 3
1 2 3 0

26

5
0 300 300 300 300
300 0 300 300 300
300 300 0 300 300
300 300 300 0 300
300 300 300 300 0

80