Dense forest in the Western suburbs helps you break loose.

西郊有密林，助君出重围。

Given a weighted undirected simple graph with vertices and positive-weighted edges. Sum up the weight of the minimum spanning forest for each of its spanning subgraph, and print the value modulo as answer.

A minimum spanning forest of a weighted undirected graph  with vertex set  and edge set  is defined as follows:

• It's a subset of  (not necessarily non-empty or different from ), denoted as .
• Any pair of vertices  which can reach each other in  can still reach each other only using edges in .
•  is the subset with minumum weight among all subsets satisfying the above two conditions. The weight of  is the sum of weight of all edges in it.

A spanning subgraph of  is a graph with vertex set  and edge set a subset of  (not necessarily non-empty or different from ).

输入描述:

The first line consists of a single integer , denoting the number of vertices in the graph.

The next  lines describes the graph with an adjacency matrix, more specifically:

Each of the  lines consists of  non-negative numbers.
The -th number of the -th line  is , if there's no edge between vertex  and ; or the weight of the only edge between them otherwise.

It's guaranteed that  and  for each , which ensures the graph is an undirected simple graph with all edges positive-weighted. It's also guaranteed that the number of edges  does not exceed .

输出描述:

Print a single integer in the first line, which is the value modulo .

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

158