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:

http://sepwww.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 guarantteed 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