Problem Description

Snuke received two matrices \( A \) and \( B \) as birthday presents. Each matrix is composed only of \( 0 \) and \( 1 \) and is an \( N \times N \) matrix.

Snuke calculated the product of the matrices \( C = AB \). All calculations were done modulo 2, so \( C \) is also an \( N \times N \) matrix composed only of \( 0 \) and \( 1 \). For \( 1 \leq i, j \leq N \), the \( (i, j) \)-th element \( c_{i, j} \) of matrix \( C \) is given.

However, Snuke accidentally ate matrices \( A \) and \( B \), so he only knows \( C \). Determine the number of possible ordered pairs of matrices \( (A, B) \) modulo \( 10^9+7 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( c_{1, 1} \) \( ... \) \( c_{1, N} \) : \( c_{N, 1} \) \( ... \) \( c_{N, N} \)

Output Format

Output the number of possible ordered pairs of matrices \( (A, B) \) modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

2
0 1
1 0

Sample Output #1

6

Sample Input #2

10
1 0 0 1 1 1 0 0 1 0
0 0 0 1 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 0 1 1 0
0 0 1 0 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 1 0 0 0 0
1 0 1 0 0 1 1 1 1 1

Sample Output #2

741992411

Notes/Hints

Constraints

• \( 1 \leq N \leq 300 \)
• \( c_{i, j} \) is either \( 0 \) or \( 1 \)

见题面 Input 部分

见题面 Output 部分