Special Matrices

题意翻译

#### 翻译： #### 题意: 一个 $n * n$ 的方阵被称为特殊的，满足下面的条件: + 它是二进制的，每一个格子上只能是$1$或者$0$。 + 每一行的和以及每列的和等于$2$ 现在，给你 $n$ 以及方阵前 $m$ 行，求前 $m$ 行与给出的 $m$ 行相同的“特殊”方阵的数量。 可能所需的答案会很大，输出其对 $mod$ 取模后的结果。(**并不保证$mod$为质数**) #### 输入格式 第一行三个整数:$n$,$m$,$mod$(表示的意义于上面题目描述) 接下来 $m$ 行，每一行给出一个长度为 $n$ 的零一串。第 $i$ 行表示方阵的第 $i$ 行，保证给出的 $m$ 行形成的 $n * m$ 的方阵每一列最多出现两个$1$，同时给出的$m$行，每一行一定包含两个$1$ 。 #### 输出格式 一行一个数，表示所需值对 $mod$ 取模后的结果。 #### 数据范围: $2 <= n <= 500$ $0 <= m <= n$ $2 <= mod <= 10^9$ #### 样例解释: 对于第一个样例，满足条件的矩阵为: ```plain Case1: Case2: 011 011 101 110 110 101 ``` 样例二：因为整个 $n$ * $n$ 的矩阵已经给出，所以只能有一种方案。

题目描述

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 $ .

输入输出格式

输入格式

The first line of the input contains three integers $ n $ , $ m $ , $ mod $ ( $ 2<=n<=500 $ , $ 0<=m<=n $ , $ 2<=mod<=10^{9} $ ). 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.

输出格式

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

输入输出样例

输入样例 #1

3 1 1000
011

输出样例 #1

2

输入样例 #2

4 4 100500
0110
1010
0101
1001

输出样例 #2

1

说明

For the first test the required matrices are: `<br></br>011<br></br>101<br></br>110<br></br><br></br>011<br></br>110<br></br>101<br></br>`In the second test the required matrix is already fully given, so the answer is 1.