题目描述
Miranda 是个热爱数学的萌妹子,然而她现在苦苦挣扎于高中数学无法自拔,于心不忍的你偷偷看了一下她的作业,发现作业本上写了两个 N×N 的元素均为 0 或 1 的矩阵 a、b,然后要算出一个 N×N 的矩阵 C,满足:
ci,j=(k=1∑Nai,kbk,j)mod2
这么简单的问题当然是难不倒 Miranda 的,你发现她在思考另外一个问题,假如现在是给定结果矩阵 C,那么会有多少种不同的有序矩阵对 (A,B),满足 A 和 B 运算后的结果恰好为 C 呢?
你发现这个问题非常有趣,于是你也陷入这个问题无法自拔了。
输入格式
第一行一个整数 N。
接下来 N 行,每行 N 个整数,对于第 i 行的第 j 的数,表示 Ci,j。
输出格式
输出一个整数,表示可能的矩阵对 (A,B) 的个数,答案模 109+7。
样例
2
0 1
1 0
6
数据范围与提示
对于 10% 的数据,N≤3;
对于 30% 的数据,N≤5;
对于 60% 的数据,N≤300;
对于 100% 的数据,1≤N≤2000,ci,j∈{0,1}。