题目描述
Problem Description
Freda has studied bitwise operations and matrices. She is now keen on delving deeper into these elegant operations and the profound structures they represent.
For a matrix composed of non-negative integers, she defines the $\texttt{AND}$ value of the matrix as the result of the binary $\texttt{AND}$ operation applied to all numbers in the matrix. Similarly, she defines the $\texttt{OR}$ value of the matrix as the result of the binary $\texttt{OR}$ operation applied to all numbers in the matrix.
Given an $N \times N$ matrix, she wishes to find:
1. The sum of the $\texttt{AND}$ values of all submatrices of the given matrix.
2. The sum of the $\texttt{OR}$ values of all submatrices of the given matrix.
You are tasked with solving this problem as Freda does not want to spend time on such straightforward tasks.
Since the answers could be very large, you only need to output the results modulo $1,000,000,007 (10^9 + 7)$.
Input Format
The first line of the input file contains a positive integer $N$, representing the size of the matrix.
The following $N$ lines each contain $N$ natural numbers, representing a row of the matrix. Adjacent numbers are separated by one or more spaces.
Output Format
The output should consist of a single line with two integers separated by a space. The first integer should be the sum of the $\texttt{AND}$ values of all submatrices modulo $10^9 + 7$, and the second integer should be the sum of the $\texttt{OR}$ values of all submatrices modulo $10^9 + 7$.
Sample Input and Output
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
Notes
Sample 1 Explanation
The $3 \times 3$ matrix has $9$ $1 \times 1$ submatrices, $6$ $1 \times 2$ submatrices, $6$ $2 \times 1$ submatrices, $4$ $2 \times 2$ submatrices, $3$ $1 \times 3$ submatrices, $3$ $3 \times 1$ submatrices, $2$ $2 \times 3$ submatrices, $2$ $3 \times 2$ submatrices, and $1$ $3 \times 3$ submatrix.
Only one submatrix (the $1 \times 1$ matrix consisting of the element in the first row and first column) has an $\texttt{AND}$ value of $1$, while all other submatrices have an $\texttt{AND}$ value of $0$, summing up to $1$.
There are $9$ submatrices containing the element in the first row and first column, each with an $\texttt{OR}$ value of $1$, while all other submatrices have an $\texttt{OR}$ value of $0$, summing up to $9$.
Data Range
| Test Point | $n$ Range | Matrix Natural Numbers Range |
|---|---|---|
| 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$ |
Additionally, there is a non-scored hack data set placed in subtask 1, with the same data range as test points 6 through 10.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分