Description

  Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含 深邃空间的结构进行更加深入的研究。
  对于一个由非负整数构成的矩阵,她定义矩阵的 AND 值为矩阵中所有数二进制 AND(&) 的运算结果;定义矩阵的 OR 值为矩阵中所有数二进制 OR(|) 的 运算结果。
给定一个 N×NN\times N 的矩阵,她希望求出:
  1. 该矩阵的所有子矩阵的AND值之和(所有子矩阵AND值相加的结果)。
  2. 该矩阵的所有子矩阵的OR值之和(所有子矩阵OR值相加的结果)。
  接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问 题,所以这个问题就交给你了。由于答案可能非常的大,你只需要输出答案对 1,000,000,007(109+7)1,000,000,007 (10^9 + 7)取模后的结果。

Input

  输入文件的第一行是一个正整数 NN,表示矩阵的尺寸。
  接下来 NN 行,每行 NN 个自然数,代表矩阵的一行。相邻两个自然数之间由 一个或多个空格隔开。

Output

  输出只有一行,包含两个用空格隔开的整数,第一个应为所有子矩阵 AND 值之和除以 109+710^9 + 7 的余数,第二个应为所有子矩阵 OR 值之和除以 109+710^9 + 7 的余 数。

Sample Input 1
3
1 0 0
0 0 0
0 0 0
Sample Output 1
1 9
Sample Input 2
3
1 2 3
4 5 6
7 8 9
Sample Output 2
73 314
Hint

样例说明 1
  该3×3矩阵共有9个1×1子矩阵、6个1×2子矩阵、6个2×1子矩阵、4 个2×2子矩阵、3个1×3子矩阵、3个3×1子矩阵、2个2×3子矩阵、2个3 ×2子矩阵和1个3×3子矩阵。
  只有一个子矩阵(仅由第一行第一列的那个元素构成的 1×1 矩阵)AND 值 为 1,其余子矩阵的 AND 值均为 0,总和为 1。
  包含第一行第一列那个元素的子矩阵有 9 个,它们的 OR 值为 1,其余子矩 阵的 OR 值为 0,总和为 9。
数据规模与约定
  所有测试数据的范围和特点如下表所示
enter image description here