分数: 1500 点
问题陈述
Snuke 收到两个矩阵 A 和 B 作为生日礼物。 每个矩阵都是一个 N by N 矩阵仅包含 0 和 1.
然后他计算了两个矩阵的乘积, C = AB。 由于他以模二执行所有计算, C 也是 N by N 矩阵仅包含 0 和 1。 对于每个 1 ≤ i, j ≤ N,给你 c_{i, j}, (i, j)- 矩阵的元素 C.
然而,Snuke不小心吃了两个矩阵 A 和 B,现在他只知道 C。 计算两个矩阵的可能(有序)对的数量 A 和 B,模数 10^9+7.
约束
- 1 ≤ N ≤ 300
- c_{i, j} 是 0 or 1.
输入
输入由标准输入按以下格式给出:
N
c_{1, 1} ... c_{1, N}
:
c_{N, 1} ... c_{N, N}
输出
打印两个矩阵的可能(有序)对的数量 A 和 B (模数 10^9+7).
示例输入 1
2 0 1 1 0
示例输出 1
6
示例输入 2
10 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1
示例输出 2
741992411