Description

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)$.

Input Format

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 Format

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$.

3
1 0 0
0 0 0
0 0 0

1 9

3
1 2 3
4 5 6
7 8 9

73 314

Hint

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

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