题目描述

你发现了一个包含 $n$ 个节点的完全无向图，节点编号为 $1 \dots n$。每条边都有一种颜色。为简单起见，每种颜色用一个介于 1 到 300 之间的整数表示。有趣的是，你注意到在该图的每一个简单环中，环上总存在两条相邻的边颜色相同。

对于图的每一个非空节点子集 $S$，记 $f(S)$ 为从 $S$ 中能够选出的最大节点子集的大小，使得所选子集中任意两个节点之间的边颜色相同。请计算所有非空节点子集 $S$ 的 $f(S)$ 之和。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$1 \leq n \leq 300$），表示图中节点的数量。

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

输出格式

输出一个整数，表示所有非空节点子集 $S$ 的 $f(S)$ 之和。由于这个数字可能非常大，请输出它对 $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

提示

翻译由 DeepSeek V3.2 完成