CF489F.Special Matrices

An n × n square matrix is special, if:

• it is binary, that is, each cell contains either a 0, or a 1;
• the number of ones in each row and column equals 2.

You are given n and the first m rows of the matrix. Print the number of special n × n matrices, such that the first m rows coincide with the given ones.

As the required value can be rather large, print the remainder after dividing the value by the given number mod.

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

• 它是二进制矩阵，即每个单元格中只包含 $0$ 或 $1$；
• 每一行和每一列中 $1$ 的个数均恰好为 $2$。

现给定 $n$ 以及该矩阵的前 $m$ 行。请输出满足以下条件的特殊 $n \times n$ 矩阵的个数：其前 $m$ 行与给定的行完全一致。

由于答案可能非常大，请输出该答案对给定模数 $\text{mod}$ 取模后的余数。

The first line of the input contains three integers n, m, mod (2 ≤ n ≤ 500, 0 ≤ m ≤ n, 2 ≤ mod ≤ 109). Then m lines follow, each of them contains n characters — the first rows of the required special matrices. Each of these lines contains exactly two characters '1', the rest characters are '0'. Each column of the given m × n table contains at most two numbers one.

输入的第一行包含三个整数 $n$、$m$、$mod$（$2 \leq n \leq 500$，$0 \leq m \leq n$，$2 \leq mod \leq 10^9$）。接下来是 $m$ 行，每行包含 $n$ 个字符——即所要求的特殊矩阵的前 $m$ 行。每行中恰好有两个字符 '1'，其余字符均为 '0'。给定的 $m \times n$ 表格中，每一列至多包含两个数字 1。

Print the remainder after dividing the required value by number mod.

输出所需值对数 mod 取模后的余数。

For the first test the required matrices are:

011
101
110

011
110
101

In the second test the required matrix is already fully given, so the answer is 1.

第一个测试用例中所需的矩阵为：

011
101
110

011
110
101

第二个测试用例中，所需的矩阵已完全给出，因此答案为 1。