#P5300. [GXOI/GZOI2019] 与或和

[GXOI/GZOI2019] 与或和

题目描述

Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含深邃空间的结构进行更加深入的研究。

对于一个由非负整数构成的矩阵,她定义矩阵的 AND\texttt{AND} 值为矩阵中所有数二进制 AND(&)\texttt{AND(\&)} 的运算结果;定义矩阵的 OR\texttt{OR} 值为矩阵中所有数二进制 OR(|)\texttt{OR(|)} 的运算结果。

给定一个 N×NN \times N 的矩阵,她希望求出:

  1. 该矩阵的所有子矩阵的 AND\texttt{AND} 值之和(所有子矩阵 AND\texttt{AND} 值相加的结果)。
  2. 该矩阵的所有子矩阵的 OR\texttt{OR} 值之和(所有子矩阵 OR\texttt{OR} 值相加的结果)。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题,所以这个问题就交给你了。

由于答案可能非常的大,你只需要输出答案对 1,000,000,007(109+7)1,000,000,007 (10^9 + 7) 取模后的结果。

输入格式

输入文件的第一行是一个正整数 NN,表示矩阵的尺寸。

接下来 NN 行,每行 NN 个自然数,代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。

输出格式

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

3
1 0 0
0 0 0
0 0 0
1 9
3
1 2 3
4 5 6
7 8 9
73 314

提示

样例1解释

3×33 \times 3 矩阵共有 991×11 \times 1 子矩阵、661×21 \times 2 子矩阵、662×12 \times 1 子矩阵、442×22 \times 2 子矩阵、3 个 1×31 \times 3 子矩阵、333×13 \times 1 子矩阵、222×32 \times 3 子矩阵、223×23 \times 2 子矩阵和 113×33 \times 3 子矩阵。
只有一个子矩阵(仅由第一行第一列的那个元素构成的 1×11 \times 1 矩阵)AND\texttt{AND} 值为 11,其余子矩阵的 AND\texttt{AND} 值均为 00,总和为 11
包含第一行第一列那个元素的子矩阵有 99 个,它们的 OR\texttt{OR} 值为 11,其余子矩阵的 OR\texttt{OR} 值为 00,总和为 99

数据范围

测试点编号 nn 的规模 矩阵中的自然数
11 1n101 \le n \le 10 100\le 100
22
33 1n1001 \le n \le 100
44
55
66 1n1,0001 \le n \le 1,000 2311\le 2^{31} - 1
77
88
99
1010

另外有一组不计分的 hack 数据,放在 subtask 1 中,数据范围与测试点 6106 \sim 10 一致。