### 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$

ftiasch

#### Manager

Information
 Solved Number 24 Submit Number 88
Problem Tags
dp
No tag edit access