After learning about bitwise operations and matrices, Freda decided to conduct a more in-depth study of these concise and elegant operations, as well as the structures that contain profound spatial properties.

For a matrix composed of non-negative integers, she defines the AND value of the matrix as the result of the bitwise AND (&) operation of all numbers in the matrix; she defines the OR value of the matrix as the result of the bitwise OR (|) operation of all numbers in the matrix.

Given an $N \times N$ matrix, she wants to find: 1. The sum of the AND values of all submatrices of the matrix (the result of adding the AND values of all submatrices). 2. The sum of the OR values of all submatrices of the matrix (the result of adding the OR values of all submatrices).

As you might have guessed, Freda does not want to spend time solving such a simple problem, so she has left it to you. Since the answer can be very large, you only need to output the result modulo $1,000,000,007$ ($10^9 + 7$).

Input

The first line contains a positive integer $N$, representing the size of the matrix.

The next $N$ lines each contain $N$ natural numbers, representing a row of the matrix. Adjacent natural numbers are separated by one or more spaces.

Output

Output a single line containing two space-separated integers. The first should be the sum of the AND values of all submatrices modulo $10^9 + 7$, and the second should be the sum of the OR values of all submatrices modulo $10^9 + 7$.

Examples

Input 1

3
1 0 0
0 0 0
0 0 0

Output 1

1 9

Note 1

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.

There is only one submatrix (the $1 \times 1$ matrix consisting only of the element in the first row and first column) with an AND value of 1; the AND values of all other submatrices are 0, for a total sum of 1.

There are 9 submatrices containing the element in the first row and first column; their OR value is 1, while the OR values of all other submatrices are 0, for a total sum of 9.

Input 2

3
1 2 3
4 5 6
7 8 9

Output 2

73 314

Constraints

The range and characteristics of all test data are shown in the table below: