Permanent

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Compute \[\mathrm{perm}(A) = \sum_{\sigma \in S_n} \prod_{i = 1}^{n} A_{i, \sigma(i)} \bmod m\] where \(S_n\) is the set of all permutations of \(\{1, 2, \ldots, n\}\).

Input

The first line contains two integers \(n\) and \(m\). The following \(n\) lines denotes the matrix \(A\).

(\(1 \leq n \leq 20\), \(1 \leq m \leq 10^9\), \(0 \leq A_{i, j} \leq 10^9\))

Output

The only integer denotes \(\mathrm{perm}(A)\).

Sample Input

2 1000000000
1 2
3 4

Sample Output

10

Hint

\[\mathrm{perm}(A) = A_{1, 1} \cdot A_{1, 2} + A_{1, 2} \cdot A_{2, 1} = 10\]

Source

ftiasch

Manager

Information
Solved Number24
Submit Number88
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel