#216209. [ICPC 2017 NAIPC] Maximum Color Clique

You found a complete, undirected graph with nodes, labeled . 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 , let denote the size of the maximum subset of nodes you can choose from such that all edges between the chosen nodes are the same color. Compute the sum of over all non empty subsets 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 (), which is the number of nodes in the graph.

The next lines will each contain integers (), which is a matrix representing the colors of the edges, where is the color of the edge between node and node . It is guaranteed that the values on the diagonal will be 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 ( for ).

Output a single integer, which is the sum of over all non empty subsets of nodes in the graph. Since this number may be very large, output it modulo .

样例输入 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