Modulo Determinant

Given an (n)-order matrix (A), compute its determinant (|A|) modulo (p). The determinant is defined as ( |A| = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^{n} a_{i,\sigma(i)} ).

inputFormat

The first line contains two integers (n) and (p), where (n) is the order of matrix (A) and (p) is the modulus (a prime number). The next (n) lines each contain (n) integers representing the rows of matrix (A).

outputFormat

Output a single integer: the determinant (|A|) modulo (p).

sample

1 7
5

5