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.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
3 1 1000
011

Output
2

Input
4 4 100500
0110
1010
0101
1001

Output
1



-----Note-----

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.

Difficulty: HARD
Tags: Dynamic programming

Combinatorics
Skill types: Dynamic programming

Starter code:

Solutions:
(a, b, mod) = list(map(int, input().split()))
g = [2] * a
for i in range(b):
	t = input()
	for (x, y) in enumerate(t):
		if y == '1':
			g[x] -= 1
one = two = 0
for q in g:
	if q < 0:
		print(0)
		exit(0)
	if q == 1:
		one += 1
	if q == 2:
		two += 1
mat = [[0] * 600 for x in range(600)]
mat[0][0] = 1
for j in range(a + 1):
	for i in range(a + 1):
		if i - 2 >= 0:
			mat[i][j] += i * (i - 1) // 2 * mat[i - 2][j]
		if j - 1 >= 0:
			mat[i][j] += i * j * mat[i][j - 1]
		if j - 2 >= 0:
			mat[i][j] += j * (j - 1) // 2 * mat[i + 2][j - 2]
		mat[i][j] %= mod
print(mat[one][two])


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
dp = [[-1 for i in range(505)] for j in range(505)]

def memo(row, z, o):
	if row == n:
		if z == 0 and o == 0:
			return 1
		else:
			return 0
	if dp[z][o] != -1:
		return dp[z][o]
	if z > 1:
		dp[z][o] += z * (z - 1) // 2 * memo(row + 1, z - 2, o + 2)
		dp[z][o] %= mod
	if z >= 1 and o >= 1:
		dp[z][o] += z * o * memo(row + 1, z - 1, o)
		dp[z][o] %= mod
	if o > 1:
		dp[z][o] += o * (o - 1) // 2 * memo(row + 1, z, o - 2)
		dp[z][o] %= mod
	dp[z][o] += 1
	dp[z][o] %= mod
	return dp[z][o] % mod
(n, m, mod) = list(map(int, input().split()))
a = []
for i in range(m):
	s = list(input())
	a.append(s)
ct = [0 for i in range(n)]
for i in range(m):
	for j in range(n):
		if a[i][j] == '1':
			ct[j] += 1
z = ct.count(0)
o = ct.count(1)
ans = memo(m, z, o)
print(ans % mod)


(n, m, mod) = [int(x) for x in input().split()]
from functools import lru_cache
import sys
sys.setrecursionlimit(100000000)

@lru_cache(maxsize=None)
def rec(twos, ones):
	global mod
	if twos == 0 and ones == 0:
		return 1
	if twos == 1 and ones == 0:
		return 0
	else:
		count = 0
		if ones >= 2:
			a = ones * (ones - 1) // 2
			b = rec(twos, ones - 2)
			count += a * b % mod
		if ones >= 1 and twos >= 1:
			a = ones * twos
			b = rec(twos - 1, ones)
			count += a * b % mod
		if twos >= 2:
			a = twos * (twos - 1) // 2
			b = rec(twos - 2, ones + 2)
			count += a * b % mod
		return count % mod
matrix = []
for i in range(0, m):
	matrix.append([int(x) for x in input()])
twocount = 0
onecount = 0
for c in range(0, n):
	count = 0
	for r in range(0, m):
		if matrix[r][c] == 1:
			count += 1
	if count == 2:
		twocount += 1
	elif count == 1:
		onecount += 1
ones = onecount
twos = n - onecount - twocount
print(rec(twos, ones))


n = 0
m = 0
MOD = 0
cap = [0] * 505
ans = [[-1] * 505 for i in range(505)]

def f(one, two):
	if one == 0 and two == 0:
		return 1
	if two > len(ans[one]):
		print(str(one) + ' ' + str(two) + ' ' + len(ans[one]))
	if ans[one][two] != -1:
		return ans[one][two]
	temp = 0
	if two > 1:
		x = two * (two - 1) / 2 * f(one + 2, two - 2)
		temp += x % MOD
	if one > 1:
		x = one * (one - 1) / 2 * f(one - 2, two)
		temp += x % MOD
	if two > 0 and one > 0:
		x = one * two * f(one, two - 1)
		temp += x % MOD
	temp = temp % MOD
	ans[one][two] = temp
	return temp
temp = input().split(' ')
n = int(temp[0])
m = int(temp[1])
MOD = int(temp[2])
for i in range(0, m):
	cur = ''
	cur = input()
	for j in range(0, n):
		if cur[j] == '1':
			cap[j] += 1
n_one = 0
n_two = 0
for i in range(0, n):
	if cap[i] == 0:
		n_two += 1
	if cap[i] == 1:
		n_one += 1
print(int(f(n_one, n_two)))