The Evaluation of Determinant

The determinant is quite important in Linear Algebras, but I think that almost everyone who has ever learnt Linear Algebras is tired of the complicated and tedious calculations of determinant. Actually, it’s not the job we should do, isn’t it? As an outstanding Geek, why don’t we just ask computers to do these?


Give you a determinant D (it’s ensured that the result of it is an integer) and m, try to get the result of this determinant mod m, and m = p1 * p2 …… pn, all the pi are different. You can assume 1000 < pi < 10000, aij < 1000, and m can be fit in 32-bit signed integer.

Input two integers n and m in the first line, n represents the scale of the determinant. (n <= 100)
Then comes an n * n matrix, the determinant’s component aij means the one in row i and column j.

Output the result of the determinant D mod m.

2 1009
1 2
3 4

1007

2009 Multi-University Training Contest 2 - Host by TJU