Description

N 个男孩，N 个女孩，男孩和女孩可能是朋友，也可能不是朋友。现在要组成N 对舞伴，要求每对舞

伴都是一男一女，且他们是朋友。

统计不同配对方案的数量，因为结果很大，所以只要求除以M 的余数。

Input

第1 行，2 个整数N，M。接下来N 行，每行N 个整数Aij，表示第i 个男孩和第j 个女孩的关系。如果他们是朋友，则Aij = 1，否则Aij = 0。

Output

1 个整数，表示所求的值。

Sample Input

3 1000000000

1 1 1

1 1 1

1 1 1

Sample Output

6

Data Constraint

• 对于50% 的数据，N <= 9；

• 对于100% 的数据，1 <= N <= 20， 1 <= M <= 10^9; 0 <= Aij <= 1。

Solution

这题一看 N≤20$N/leq20$ 就知道是状压DP啦！

设 f[i][s]$f[i][s]$ 表示选了前 i$i$ 个男孩，已选女孩状态为 s$s$ 的方案数。

显然可得：f[i][s]+=f[i−1][s′]$f[i][s]+=f[i-1][s']$

每个男孩向是朋友的女孩转移即可，还可以开滚动节约空间。

总时间复杂度为 O(2N∗N2)$O(2^N*N^2)$ 。

Code