← 返回题目列表

AtCoder · cf16_exhibition_final_h

H. AB=C 问题

中文机器翻译题面 查看原题

分数: 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