BANDMATR  Determinant of Banded Matrices
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 nonzero 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
hide comments
Min_25:
20150419 13:53:47
Test cases are somewhat weak.


Chen Xiaohong:
20090701 04:23:08
Changed to 0.5 seconds. Thanks for pointing this out. 

Robert Gerbicz:
20090629 11:37:37
Please view topic: https://www.spoj.pl/forum/viewtopic.php?f=3&t=5705 Last edit: 20090629 15:52:11 

[Trichromatic] XilinX:
20090629 08:09:29
Mmm...As I mentioned in other problems, Please set the time limit to 0.5 second or more. If you want to make the time limit tight, please update more test case rather than give a very short time limit. 

Chen Xiaohong:
20090629 06:45:19
The SPOJ machine is faster than I thought ... The time limit has been made a little bit tighter to force you to use the "banded property" :).


piyifan:
20090628 13:51:22
I use the program of DETER3 got AC.Is this problem special? 

Chen Xiaohong:
20090626 18:58:04
Rejudged. 
Added by:  Chen Xiaohong 
Date:  20090626 
Time limit:  0.100s 
Source limit:  20000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  classical numerical analysis 