题目描述

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

$$c_{i, j} = \left( \sum_{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\}$。