SP4533 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 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

A total of

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