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.</p>

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 ≤ n ≤ 300), which is the number of nodes in the graph.</p>

The next n lines will each contain n integers c (0 ≤ c ≤ 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 ≤ c[x, y] = c[y, x] ≤ 300 for x ≠ 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⁹ + 7.

예제 입력 1

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

예제 출력 1

26

예제 입력 2

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

예제 출력 2

80