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。