#6040. 「雅礼集训 2017 Day5」矩阵

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Miranda 是个热爱数学的萌妹子,然而她现在苦苦挣扎于高中数学无法自拔,于心不忍的你偷偷看了一下她的作业,发现作业本上写了两个 N \times N 的元素均为 0 1 的矩阵 a b ,然后要算出一个 N \times N 的矩阵 C ,满足:

c_{i, j} = \left ( \sum\limits_{k = 1} ^ N a_{i, k} b_{k, j} \right ) \bmod 2

这么简单的问题当然是难不倒 Miranda 的,你发现她在思考另外一个问题,假如现在是给定结果矩阵 C ,那么会有多少种不同的有序矩阵对 (A, B) ,满足 A B 运算后的结果恰好为 C 呢?

你发现这个问题非常有趣,于是你也陷入这个问题无法自拔了。

输入格式

第一行一个整数 N
接下来 N 行,每行 N 个整数,对于第 i 行的第 j 的数,表示 C_{i, j}

输出格式

输出一个整数,表示可能的矩阵对 (A, B) 的个数,答案模 10 ^ 9 + 7

样例

样例输入

2
0 1
1 0

样例输出

6

数据范围与提示

对于 10\% 的数据, N \leq 3
对于 30\% 的数据, N \leq 5
对于 60\% 的数据, N \leq 300
对于 100\% 的数据, 1 \leq N \leq 2000, c_{i, j} \in \{ 0, 1 \}