P5300 [GXOI/GZOI2019] AND and OR Sum

After learning bitwise operations and matrices, Freda decided to further study these simple and elegant operations, as well as the structures that contain profound spaces. For a matrix consisting of non-negative integers, she defines the $\texttt{AND}$ value of the matrix as the result of applying bitwise $\texttt{AND(\&)}$ to all numbers in the matrix; she defines the $\texttt{OR}$ value of the matrix as the result of applying bitwise $\texttt{OR(|)}$ to all numbers in the matrix. Given an $N \times N$ matrix, she wants to compute: 1. The sum of the $\texttt{AND}$ values of all submatrices (the result of adding up the $\texttt{AND}$ values of all submatrices). 2. The sum of the $\texttt{OR}$ values of all submatrices (the result of adding up the $\texttt{OR}$ values of all submatrices). You can probably guess what happens next—Freda does not want to spend time solving such a simple problem, so she leaves it to you. Since the answer may be very large, you only need to output the result modulo $1,000,000,007 (10^9 + 7)$.

The first line of the input file contains a positive integer $N$, which denotes the size of the matrix. The next $N$ lines each contain $N$ natural numbers, representing one row of the matrix. Any two adjacent natural numbers are separated by one or more spaces.

Output a single line containing two integers separated by a space. The first should be the remainder when the sum of $\texttt{AND}$ values of all submatrices is taken modulo $10^9 + 7$, and the second should be the remainder when the sum of $\texttt{OR}$ values of all submatrices is taken modulo $10^9 + 7$.

### Explanation of Sample 1 This $3 \times 3$ matrix has $9$ submatrices of size $1 \times 1$, $6$ submatrices of size $1 \times 2$, $6$ submatrices of size $2 \times 1$, $4$ submatrices of size $2 \times 2$, $3$ submatrices of size $1 \times 3$, $3$ submatrices of size $3 \times 1$, $2$ submatrices of size $2 \times 3$, $2$ submatrices of size $3 \times 2$, and $1$ submatrix of size $3 \times 3$. Only one submatrix (the $1 \times 1$ matrix consisting only of the element in the first row and first column) has an $\texttt{AND}$ value of $1$; all other submatrices have an $\texttt{AND}$ value of $0$, so the total sum is $1$. There are $9$ submatrices that contain the element in the first row and first column. Their $\texttt{OR}$ value is $1$, while all other submatrices have an $\texttt{OR}$ value of $0$, so the total sum is $9$. ### Constraints |Test Point ID|Scale of $n$|Natural numbers in the matrix| |:-:|:-:|:-:| |$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$| In addition, there is a set of unscored hack testdata placed in subtask 1, with the same constraints as test points $6 \sim 10$. Translated by ChatGPT 5