题目描述

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 $。

样例

input

2
0 1
1 0

output

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 } $。