你发现了一个包含 $n$ 个节点的完全无向图，节点编号为 $1 \dots n$。每条边都有一个颜色。为了简化起见，每种颜色由 $1$ 到 $300$ 之间（包含 $1$ 和 $300$）的一个数字标识。有趣的是，你注意到在这个图中，对于每一个简单环，该环上总有两条相邻的边颜色相同。

对于图中每一个非空节点子集 $S$，令 $f(S)$ 表示你可以从 $S$ 中选择的满足以下条件的最大子集的大小：该子集中任意两点之间的边颜色相同。计算图中所有非空节点子集 $S$ 的 $f(S)$ 之和。

输入格式

每个输入包含一组测试数据。注意你的程序可能会在不同的输入上运行多次。输入的第一行包含一个整数 $n$ ($1 \le n \le 300$)，表示图中的节点数。

接下来的 $n$ 行，每行包含 $n$ 个整数 $c$ ($0 \le c \le 300$)，这是一个表示边颜色的矩阵，其中 $c[x, y]$ 是节点 $x$ 和节点 $y$ 之间边的颜色。保证对角线上的值为 $0$ ($c[x, x] = 0$)，因为节点到自身没有边。同时保证矩阵是对称的，且非对角线上的颜色范围在 $1$ 到 $300$ 之间 ($1 \le c[x, y] = c[y, x] \le 300$，当 $x \neq y$ 时)。

输出格式

输出一个整数，即图中所有非空节点子集 $S$ 的 $f(S)$ 之和。由于这个数字可能非常大，请输出其对 $10^9 + 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