Submatrix Bitwise AND and OR Sums

Freda has been fascinated by the elegance of bitwise operations and the deep structures hidden in matrices. For a matrix consisting of non‐negative integers, she defines the AND value of a submatrix as the result of applying the binary AND operation on all of its elements, and the OR value as the result of applying the binary OR operation on all of its elements.

Given an N × N matrix, your task is to compute the following:

1. The sum of the AND values of all submatrices.
2. The sum of the OR values of all submatrices.

Since the answers might be extremely large, report each of them modulo \(10^9+7\).

Note: A submatrix is defined by choosing some top, bottom, left, and right boundaries (with 1 ≤ top ≤ bottom ≤ N and 1 ≤ left ≤ right ≤ N).

In other words, if we denote the matrix as \(A\) with elements \(A_{ij}\), then for any submatrix defined by rows \([r_1, r_2]\) and columns \([c_1, c_2]\):

• Its AND value is \(\bigwedge_{i=r_1}^{r_2}\bigwedge_{j=c_1}^{c_2} A_{ij}\)
• Its OR value is \(\bigvee_{i=r_1}^{r_2}\bigvee_{j=c_1}^{c_2} A_{ij}\)

Your program should compute the sum of the AND values and the sum of the OR values over all possible submatrices, each taken modulo 10^9+7.

inputFormat

The first line contains an integer N representing the dimensions of the square matrix. Each of the next N lines contains N non-negative integers separated by spaces, representing the matrix.

For example:

2
1 2
3 4

outputFormat

Output two space‐separated integers: the sum of the AND values of all submatrices and the sum of the OR values of all submatrices, each taken modulo \(10^9+7\).

sample

2
1 2
3 4

11 36