题目描述
Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。
对于一个由非负整数构成的矩阵，她定义矩阵的AND值为矩阵中所有数二进制AND(&)的运算结果；定义矩阵的OR值为矩阵中所有数二进制OR(|)的运算结果。
给定一个$N \times N$的矩阵，她希望求出： 1. 该矩阵的所有子矩阵的AND值之和（所有子矩阵AND值相加的结果）。 2. 该矩阵的所有子矩阵的OR值之和（所有子矩阵OR值相加的结果）。
接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。
由于答案可能非常的大，你只需要输出答案对$1,000,000,007 (10^9 + 7)$取模后的结果。
输入输出格式
输入格式
输入文件的第一行是一个正整数$N$，表示矩阵的尺寸。
接下来$N$行，每行$N$个自然数，代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。
输出格式
输出只有一行，包含两个用空格隔开的整数，第一个应为所有子矩阵AND值之和除以$10^9 + 7$的余数，第二个应为所有子矩阵OR值之和除以$10^9 + 7$的余数。
输入输出样例
输入样例 #1
3
1 0 0
0 0 0
0 0 0输出样例 #1
1 9输入样例 #2
3
1 2 3
4 5 6
7 8 9输出样例 #2
73 314说明/提示
样例1解释
该$3 \times 3$矩阵共有$9$个$1 \times 1$子矩阵、$6$个$1 \times 2$子矩阵、$6$个$2 \times 1$子矩阵、$4$个$2 \times 2$子矩阵、3 个$1\times 3$子矩阵、$3$个$3 \times 1$子矩阵、$2$个$2 \times 3$子矩阵、$2$个$3 \times 2$子矩阵和$1$个$3 \times 3$子矩阵。
只有一个子矩阵（仅由第一行第一列的那个元素构成的$1 \times 1$矩阵）AND值为$1$，其余子矩阵的$AND值均为$0$，总和为$1$。
包含第一行第一列那个元素的子矩阵有$9$个，它们的OR值为$1$，其余子矩阵的OR值为$0$，总和为$9$。
数据范围
| 测试点编号 | $n$的规模 | 矩阵中的自然数 |
|---|---|---|
| $1$ | $1 \le n \le 10$ | $\le 100$ |
| $2$ | $1 \le n \le 10$ | $\le 100$ |
| $3$ | $1 \le n \le 100$ | $\le 100$ |
| $4$ | $1 \le n \le 100$ | $\le 100$ |
| $5$ | $1 \le n \le 100$ | $\le 100$ |
| $6$ | $1 \le n \le 1,000$ | $\le 2^{31} - 1$ |
| $7$ | $1 \le n \le 1,000$ | $\le 2^{31} - 1$ |
| $8$ | $1 \le n \le 1,000$ | $\le 2^{31} - 1$ |
| $9$ | $1 \le n \le 1,000$ | $\le 2^{31} - 1$ |
| $10$ | $1 \le n \le 1,000$ | $\le 2^{31} - 1$ |
另外有一组不计分的 hack 数据，放在 subtask 1 中，数据范围与测试点$6 \sim 10$一致。