← 返回题目列表

Codeforces · 489/F

F. 特殊矩阵

中文机器翻译题面 查看原题

n × n 方阵是特殊的,如果:

- 它是二进制的,即每个单元格包含一个 0 或一个 1;
- 每行和每列中的个数等于 2。

给定矩阵的 n 行和前 m 行。打印特殊 n × n 矩阵的数量,使得前 m 行与给定的行一致。

由于所需的值可能相当大,因此打印该值除以给定数字 mod 后的余数。

输入

输入的第一行包含三个整数 n、m、mod (2 ≤ n ≤ 500、0 ≤ m ≤ n、2 ≤ mod ≤ 109)。接下来是 m 行,每行包含 n 个字符——所需特殊矩阵的第一行。每行都包含两个字符“1”,其余字符为“0”。给定的 m × n 表的每一列最多包含两个数字 1。

输出

打印所需值除以 number mod 后的余数。

示例

输入 #1

3 1 1000
011

输出 #1

2

输入 #2

4 4 100500
0110
1010
0101
1001

输出 #2

1

注意

对于第一个测试,所需的矩阵是:

在第二个测试中,所需的矩阵已经完全给出,所以答案是 1。