题目描述

一个 $n \times n$ 的方阵被称为特殊的，满足下面的条件：

• 它是二进制的，每一个格子上只能是 $1$ 或者 $0$。
• 每一行的和以及每列的和等于 $2$。

现在，给你 $n$ 以及方阵前 $m$ 行，求前 $m$ 行与给出的 $m$ 行相同的特殊方阵的数量。

可能所需的答案会很大，输出其对 $mod$ 取模后的结果。并不保证 $mod$ 为质数。

输入格式

第一行三个整数：$n,m,mod$，$2 \le n \le 500$，$0 \le m \le n$，$2 \le mod \le 10^9$。

接下来 $m$ 行，每一行给出一个长度为 $n$ 的零一串。第 $i$ 行表示方阵的第 $i$ 行，保证给出的 $m$ 行形成的 $n \times m$ 的方阵每一列最多出现两个 $1$，同时给出的 $m$ 行，每一行一定包含两个 $1$。

输出格式

一行一个数，表示所需值对 $mod$ 取模后的结果。

3 1 1000
011

2

对于第一个样例，满足条件的矩阵为:

Case1:  Case2:
 011     011
 101     110
 110     101

4 4 100500
0110
1010
0101
1001

1

因为整个 $n \times n$ 的矩阵已经给出，所以只能有一种方案。