Computing the determinant of a matrix using Gaussian elimination takes O(n^3). On the other hand, computing the determinant of tridiagonal matrix is O(n) using a recurrence. In this problem you will compute the determinant of banded matrices. A band matrix is a sparse matrix, whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side. In this problem, given a banded NxN square integer matrix with M bands on each side of the diagonal, we ask you to compute the determinant of this matrix. For example a tridiagonal matrix has exactly 1 band on each side, and the 8x8 Matrix in the sample input has 2 bands on each side. For a good discussion of banded matrices, see Thorson's paper at: www.stanford.edu/oldreports/sep20/20_11_abs.html

Input

A total of < 10 inputs. For each input,

First line has dimension, N (1 < N < 501), of the matrix, followed by N lines with N integers, each less than 10001, and greater than -10001. It is guaranteed that the number of bands on each side of the diagonal, M < 51. That is there are at most 101 bands in total including the diagonal. Use scanf IO, and avoid stl IO.

Output

For each input matrix, output its determinant modulo 10^9+7.

Hint: Use Montgomery multiplication for fast computation, i.e., see: http://everything2.com/title/Montgomery%2520multiplication

Example

Input:
2
2 0
0 2
2
1 0
0 1
8
1 0 -1 0 0 0 0 0
-1 1 0 -1 0 0 0 0
-1 0 -1 1 -1 0 0 0
0 -1 0 -1 0 -1 0 0
0 0 -1 0 1 0 -1 0
0 0 0 -1 -1 1 0 -1
0 0 0 0 -1 0 -1 1
0 0 0 0 0 -1 0 -1

Output:
4
1
36