Problem H
Maximum Color Clique

You found a complete, undirected graph with $n$ nodes, labeled $1$ to $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 at least 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.

Input

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 \le n \le 300$), which is the number of nodes in the graph.

The next $n$ lines will each contain $n$ integers $c$ ($0 \le c \le 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 \le c[x,y] = c[y,x] \le 300$ for $x \ne y$).

Output

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