Educational DP Contest - Matching

There are N men and N women, both numbered 1, 2, \ldots, N.

For each i, j (1 \leq i, j \leq N), the compatibility of Man i and Woman j is given as an integer a_{i, j}. If a_{i, j} = 1, Man i and Woman j are compatible; if a_{i, j} = 0, they are not.

Taro is trying to make N pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.

Find the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Constraints

* All values in input are integers.
* 1 \leq N \leq 21
* a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:


N
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}


Output

Print the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Examples

Input

3
0 1 1
1 0 1
1 1 1


Output

3


Input

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0


Output

1


Input

1
0


Output

0


Input

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0


Output

102515160

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def popcount(i):
	assert 0 <= i < 4294967296
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * 2 ** N
dp[0] = 1
for S in range(1, 2 ** N):
	p = popcount(S)
	j = S & -S
	S2 = S
	for _ in range(p):
		if A[p - 1][j.bit_length() - 1]:
			dp[S] = (dp[S - j] + dp[S]) % mod
		S2 -= j
		j = S2 & -S2
print(dp[-1])


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
for i in range(1, 1 << n):
	k = bin(i).count('1')
	for j in range(n):
		if i >> j & 1 and a[k - 1][j]:
			dp[i] += dp[i ^ 1 << j]
	dp[i] %= mod
print(dp[(1 << n) - 1])


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
memo = [-1] * (1 << n)
memo[0] = 1

def dfs(s, count):
	if memo[s] != -1:
		return memo[s]
	res = 0
	for i in range(n):
		if s >> i & 1 and a[count - 1][i]:
			res += dfs(s ^ 1 << i, count - 1)
	memo[s] = res % mod
	return memo[s]
print(dfs((1 << n) - 1, n))


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * (1 << n) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for bit in range(1 << n):
		if not dp[i][bit]:
			continue
		for k in range(n):
			if not bit & 1 << k and A[i][k]:
				dp[i + 1][bit | 1 << k] += dp[i][bit]
				dp[i + 1][bit | 1 << k] %= mod
print(dp[n][(1 << n) - 1])


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (1 << n)
dp[0] = 1
for bit in range(1, 1 << n):
	i = bin(bit).count('1')
	for j in range(n):
		if bit >> j & 1 and a[i - 1][j]:
			dp[bit] += dp[bit ^ 1 << j]
	dp[bit] %= mod
print(dp[-1])


n = int(input())
A = [int(input().replace(' ', ''), 2) for _ in [0] * n]
dp = [0] * 2 ** n
dp[0] = 1
for I in range(2 ** n - 1):
	a = A[bin(I).count('1')] & ~I
	for j in range(n):
		if a & 1 << j:
			dp[I | 1 << j] = (dp[I | 1 << j] + dp[I]) % (10 ** 9 + 7)
print(dp[-1])


def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def count_bits(N):
	T = 0
	while N != 0:
		T += N & 1
		N >>= 1
	return T

def solve():
	N = read_int()
	modulo = 10 ** 9 + 7
	A = []
	for _ in range(N):
		A.append(read_ints())
	dp = [0] * 2 ** N
	dp[0] = 1
	for mask in range(2 ** N - 1):
		a = count_bits(mask)
		for b in range(N):
			if A[a][b] and mask & 1 << b == 0:
				dp[mask | 1 << b] = (dp[mask | 1 << b] + dp[mask]) % modulo
	return dp[-1]
print(solve())


def main():
	n = int(input())
	a = [list(map(int, input().split())) for _ in range(n)]
	MOD = 10 ** 9 + 7
	dp = [0] * (1 << n)
	pair_dic = {}
	for i in range(n + 1):
		pair_dic[i] = []
	for i in range(1 << n):
		pair_dic[bin(i).count('1')].append(i)
	dp[0] = 1
	for i in range(n):
		for k in range(n):
			if a[i - 1][k] == 0:
				continue
			for j in pair_dic[i]:
				if (j & 1 << k) >> k == 0:
					dp[j + (1 << k)] += dp[j]
					dp[j + (1 << k)] = dp[j + (1 << k)] % MOD
	print(dp[-1])
main()


import sys

def main():
	MOD = 10 ** 9 + 7
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	NI = lambda : int(sys.stdin.readline())
	N = NI()
	a = [LI() for _ in range(N)]
	dp = [[0] * 2 ** N for _ in range(N)]
	q = [[] for _ in range(N)]
	b = 1
	for i in range(N):
		if a[0][i]:
			dp[0][b] = 1
			q[0].append(b)
		b <<= 1
	for i in range(1, N):
		for k in q[i - 1]:
			v = dp[i - 1][k]
			b = 1
			for l in a[i]:
				if l and k & b == 0:
					m = k | b
					if dp[i][m] == 0:
						q[i].append(m)
					dp[i][m] = (dp[i][m] + v) % MOD
				b <<= 1
	print(dp[-1][2 ** N - 1])
main()


(N,) = map(int, input().split())
M = 10 ** 9 + 7
n = N
_ALL = 1 << n

def itercomb(n, k):
	if k == 0:
		yield 0
	else:
		_a = (1 << k) - 1
		yield _a
		while 1:
			_x = _a & -_a
			_y = _a + _x
			_a = (_a & ~_y) // _x >> 1 | _y
			if _a >= _ALL:
				break
			yield _a
xs = []
for _ in range(N):
	xs.append([1 << i for (i, x) in enumerate(input().split()) if int(x)])
d = [0] * (1 << N)
d[0] = 1
for (i, y) in enumerate(xs):
	for x in itercomb(N, i):
		for ai in y:
			if not x & ai:
				d[x | ai] = (d[x] + d[x | ai]) % M
print(d[-1])


n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (1 << n)
dp[0] = 1
for i in range(n):
	dp2 = [0] * (1 << n)
	for j in range(1 << n):
		if dp[j] == 0:
			continue
		for k in range(n):
			if j >> k & 1 == 0:
				dp2[j | 1 << k] += dp[j] * a[i][k]
				dp2[j | 1 << k] %= mod
	dp = dp2
print(dp[-1])


import sys
input = sys.stdin.buffer.readline

def main():
	N = int(input())
	a = [list(map(int, input().split())) for _ in range(N)]
	MOD = 10 ** 9 + 7
	dp = [1] + [0] * (1 << N)
	for i in range(N):
		use = [0] * ((1 << N) + 1)
		for s in range(1 << N):
			if dp[s] == 0:
				continue
			for j in range(N):
				jb = 1 << j
				if not s & jb and a[i][j]:
					use[s ^ jb] += dp[s]
		dp = use
	print(dp[(1 << N) - 1] % MOD)
main()


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	(n, k) = LI()
	a = LI()
	dp = [0 for i in range(k + 1)]
	f = [0 for i in range(k + 1)]
	for i in range(k + 1):
		if not f[i]:
			for j in a:
				if i - j >= 0:
					dp[i] = 1 - dp[i - j]
					if dp[i] == 0:
						break
			else:
				dp[i] = 1
	print(['First', 'Second'][dp[k]])

def B():
	n = I()
	a = LI()
	ma = n * (n + 1) // 2
	su = sum(a)
	s = [1 for i in range(n + 1)]
	for i in range(1, n):
		s[i + 1] = s[i] + n - i + 1
	d = [None for i in range(ma + 1)]
	d[0] = 0
	k = 1
	for i in range(1, n + 1):
		for j in range(n + 1 - i):
			d[k + j] = i
		k += n + 1 - i
	k = n % 2
	dp = [su if (d[i] + k) % 2 else -su for i in range(ma + 1)]
	dp[0] = 0
	if k:
		for i in range(n):
			dp[i + 1] = a[n - 1 - i]
	else:
		for i in range(n):
			dp[i + 1] = -a[n - 1 - i]
	for i in range(1, ma):
		r = n - 1 - (i - s[d[i]])
		l = r + 1 - d[i]
		j = i + (n - d[i])
		j2 = j + 1
		if (d[i] + k) % 2:
			if r < n - 1:
				if a[r + 1] + dp[i] > dp[j]:
					dp[j] = a[r + 1] + dp[i]
			if l > 0:
				if a[l - 1] + dp[i] > dp[j2]:
					dp[j2] = a[l - 1] + dp[i]
		else:
			if r < n - 1:
				if -a[r + 1] + dp[i] < dp[j]:
					dp[j] = -a[r + 1] + dp[i]
			if l > 0:
				if -a[l - 1] + dp[i] < dp[j2]:
					dp[j2] = -a[l - 1] + dp[i]
	print(dp[ma])
	return

def C():

	def comb(a, b):
		return fact[a] * inv[b] * inv[a - b] % mod
	(n, k) = LI()
	a = LI()
	dp = [[0] * (k + 1) for i in range(n + 1)]
	for i in range(k + 1):
		dp[0][i] = 1
	for i in range(n):
		ni = i + 1
		ai = a[i]
		for j in range(k + 1):
			if j >= ai + 1:
				dp[ni][j] = (dp[i][j] - dp[i][j - ai - 1]) % mod
			else:
				dp[ni][j] = dp[i][j]
		if i < n - 1:
			for j in range(k):
				dp[ni][j + 1] += dp[ni][j]
				dp[ni][j + 1] %= mod
	print(dp[n][k] % mod)
	return

def D():
	n = I()
	a = LI()
	a.insert(0, 0)
	for i in range(n):
		a[i + 1] += a[i]
	dp = [[0] * (n + 1) for i in range(n)]
	for le in range(1, n):
		for l in range(n - le):
			r = l + le + 1
			res = float('inf')
			for i in range(l + 1, r):
				m = dp[l][i] + dp[i][r]
				if m < res:
					res = m
			res += a[r] - a[l]
			dp[l][r] = res
	print(dp[0][n])
	return

def E():

	def bit_count(n):
		return bin(n).count('1')
	n = I()
	a = LIR(n)
	m = 1 << n
	dp = [0] * m
	dp[0] = 1
	a = [[j for j in range(n) if a[i][j]] for i in range(n)]
	for k in range(1, m):
		i = bit_count(k) - 1
		for j in a[i]:
			bj = 1 << j
			if bj > k:
				break
			if not k & bj:
				continue
			nk = k ^ bj
			dp[k] += dp[nk]
			dp[k] %= mod
	print(dp[m - 1])

def F():
	return

def G():
	return

def H():
	return
E()


import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	popcount_to_state = [[] for _ in range(n + 1)]
	for U in range(1 << n):
		popcount_to_state[bin(U).count('1')].append(U)
	dp = [0] * (1 << n)
	dp[0] = 1
	for i in range(n):
		A = tuple(map(int, input().split()))
		for j in range(n):
			if not A[j]:
				continue
			for U in popcount_to_state[i]:
				if U >> j & 1:
					continue
				nU = U | 1 << j
				dp[nU] += dp[U]
				if dp[nU] >= MOD:
					dp[nU] -= MOD
	print(dp[-1])
resolve()


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def count_bit_flag(T):
	T = (T & 1431655765) + (T >> 1 & 1431655765)
	T = (T & 858993459) + (T >> 2 & 858993459)
	T = (T & 252645135) + (T >> 4 & 252645135)
	T = (T & 16711935) + (T >> 8 & 16711935)
	T = (T & 65535) + (T >> 16 & 65535)
	return T

def main():
	N = int(input())
	A = tuple((tuple(map(int, input().split())) for _ in range(N)))
	memo = {i: set() for i in range(N)}
	for bit in range(1, 1 << N):
		memo[count_bit_flag(bit) - 1].add(bit)
	dp = [0] * (1 << N)
	dp[0] = 1
	for (i, bit_list) in enumerate(memo.values()):
		for bit in bit_list:
			for (j, a) in enumerate(A[i]):
				if a and bit >> j & 1:
					dp[bit] += dp[bit ^ 1 << j]
					dp[bit] %= mod
	print(dp[(1 << N) - 1])
main()


def main():
	n = int(input())
	mod = 10 ** 9 + 7
	a = []
	for i in range(n):
		a.extend(list(map(int, input().split())))
	dp = [0] * (1 << n)
	dp[0] = 1
	for S in range((1 << n) - 1):
		k = bin(S).count('1') * n
		t = dp[S]
		for i in range(n):
			if a[k + i]:
				dp[S | 1 << i] = (dp[S | 1 << i] + t) % mod
	print(dp[(1 << n) - 1])
main()


import sys
sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.buffer.readline

def even(n):
	return 1 if n % 2 == 0 else 0
mod = 10 ** 9 + 7
n = int(readline())
mens = []
for i in range(n):
	s = readline().rstrip().decode('utf-8')
	s = ''.join(s.split(' '))
	res = int(s, 2)
	mens.append(res)
dp = [-1 for _ in range(1 << n)]
dp[-1] = 1

def rec(s, v):
	if dp[s] != -1:
		return dp[s]
	res = 0
	for u in range(n):
		if s >> u & 1 == 0 and mens[v] >> u & 1 == 1:
			res += rec(s | 1 << u, v + 1)
	dp[s] = res % mod
	return dp[s]
print(rec(0, 0))


import sys
input = sys.stdin.readline
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1

def bitcount(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
for n in range(1 << N):
	i = bitcount(n)
	c = dp[n]
	tmp = n
	tmp ^= (1 << N) - 1
	for j in range(N):
		r = 1 & tmp
		if r == 1 and a[i - 1][j] == 1:
			nc = dp[n + (1 << j)] + c
			if nc >= mod:
				nc -= mod
			dp[n + (1 << j)] = nc
		tmp = tmp >> 1
		if tmp == 0:
			break
print(dp[-1])


def bitcount(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
MOD = 10 ** 9 + 7
n = int(input())
can = [[int(i) for i in input().split()] for j in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
for mask in range((1 << n) - 1):
	a = bin(mask).count('1')
	for b in range(n):
		if can[a][b] and (not mask & 1 << b):
			mask2 = mask ^ 1 << b
			dp[mask2] += dp[mask]
			if dp[mask2] >= MOD:
				dp[mask2] -= MOD
print(dp[(1 << n) - 1])


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
MOD = 10 ** 9 + 7
dp = [-1] * (1 << n)
dp[0] = 1

def dfs(state, c):
	if dp[state] != -1:
		return dp[state]
	ret = 0
	for i in range(n):
		if state & 1 << i and a[c][i]:
			ret += dfs(state ^ 1 << i, c + 1)
	dp[state] = ret % MOD
	return dp[state]
print(dfs((1 << n) - 1, 0))


mod = 10 ** 9 + 7
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
dp = [-1 for __ in range(1 << n)]
dp[0] = 1

def dfs(bit, i):
	if dp[bit] != -1:
		return dp[bit]
	else:
		tmp = 0
		for j in range(n):
			if bit & 1 << j and a[i][j]:
				tmp += dfs(bit ^ 1 << j, i + 1)
	dp[bit] = tmp % mod
	return dp[bit]
print(dfs(2 ** n - 1, 0))


import itertools
MOD = 10 ** 9 + 7

def main():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	dp = [[0] * (1 << N) for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(N):
		pairs = []
		for j in range(N):
			if A[i][j] == 1:
				pairs.append(1 << j)
		for combi in itertools.combinations(range(N), r=i):
			x = 0
			for c in combi:
				x += 1 << c
			for p in pairs:
				if x & p == 0:
					dp[i + 1][x | p] = (dp[i + 1][x | p] + dp[i][x]) % MOD
	print(dp[N][(1 << N) - 1])
main()


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
memo = [-1] * (1 << N)
memo[0] = 1

def dfs(state, c):
	if memo[state] != -1:
		return memo[state]
	r = 0
	for i in range(N):
		if state & 1 << i and A[c][i]:
			r += dfs(state ^ 1 << i, c + 1)
	memo[state] = r = r % MOD
	return r
print(dfs((1 << N) - 1, 0))


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
DP = [-1] * (1 << N)

def f(x, k):
	if x == 0:
		DP[x] = 1
	if DP[x] != -1:
		return DP[x]
	DP[x] = 0
	for i in range(N):
		if x & 1 << i:
			if A[k][i]:
				DP[x] += f(x ^ 1 << i, k + 1)
	return DP[x]
print(f((1 << N) - 1, 0) % (10 ** 9 + 7))


N = int(input())
dp = [0] * (1 << N)
dp[0] = 1
MOD = 10 ** 9 + 7
now = {0}
for _ in range(N):
	mat = [1 << i for (i, v) in enumerate(input().split()) if v == '1']
	nxt = set()
	for k in now:
		p = dp[k] % MOD
		for m in mat:
			if k & m:
				continue
			dp[k | m] += p
			nxt.add(k | m)
	now = nxt
print(dp[-1] % MOD)


import sys
input = sys.stdin.readline
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10 ** 9 + 7
DPLIST = [-1] * 2 ** N
DPLIST[2 ** N - 1] = 1

def dp(NOW, x):
	if DPLIST[NOW] != -1:
		return DPLIST[NOW]
	ANS = 0
	for i in range(N):
		if A[x][i] == 1 and NOW & 1 << i == 0:
			ANS += dp(NOW + (1 << i), x + 1)
	ANS %= mod
	DPLIST[NOW] = ANS
	return ANS
print(dp(0, 0))


from itertools import combinations

def solve():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	mod = 10 ** 9 + 7
	dp = [0] * (1 << N)
	dp[0] = 1
	for i in range(N):
		for com in combinations(range(N), i + 1):
			S = 0
			for k in com:
				S += 1 << k
			for j in com:
				dp[S] += dp[S - (1 << j)] * A[i][j]
				dp[S] %= mod
	return dp[-1]
print(solve())


def main():
	mod = 10 ** 9 + 7
	N = int(input())
	a = [list(map(int, input().split())) for _ in range(N)]
	dp = [0] * (1 << N)
	dp[0] = 1

	def bitcount(i):
		i = i - (i >> 1 & 1431655765)
		i = (i & 858993459) + (i >> 2 & 858993459)
		return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
	for s in range(1, 1 << N):
		women = []
		m = bitcount(s) - 1
		for w in range(N):
			if a[m][w] == 1 and s & 1 << w:
				dp[s] += dp[s ^ 1 << w]
				dp[s] %= mod
	print(dp[-1])
main()


def examA():
	N = I()
	H = LI()
	dp = [inf] * N
	dp[0] = 0
	for i in range(N - 1):
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(H[i + 1] - H[i]))
		if i < N - 2:
			dp[i + 2] = min(dp[i + 2], dp[i] + abs(H[i + 2] - H[i]))
	ans = dp[-1]
	print(ans)
	return

def examB():
	(N, K) = LI()
	H = LI()
	dp = [inf] * N
	dp[0] = 0
	for i in range(N):
		for k in range(1, K + 1):
			if i + k >= N:
				break
			if dp[i + k] > dp[i] + abs(H[i + k] - H[i]):
				dp[i + k] = dp[i] + abs(H[i + k] - H[i])
	ans = dp[-1]
	print(ans)
	return

def examC():
	N = I()
	A = [0] * N
	B = [0] * N
	C = [0] * N
	for i in range(N):
		(A[i], B[i], C[i]) = LI()
	dp = [[0] * 3 for _ in range(N + 1)]
	for i in range(N):
		dp[i + 1][0] = max(dp[i][1], dp[i][2]) + A[i]
		dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
		dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
	ans = max(dp[N])
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	S = SI()
	N = len(S)
	T = SI()
	M = len(T)
	dp = [[0] * (M + 1) for _ in range(N + 1)]
	for i in range(N):
		for j in range(M):
			if S[i] == T[j]:
				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
	i = N
	j = M
	ans = []
	while i > 0 and j > 0:
		if dp[i][j] == dp[i - 1][j]:
			i -= 1
		elif dp[i][j] == dp[i][j - 1]:
			j -= 1
		else:
			ans.append(S[i - 1])
			i -= 1
			j -= 1
	print(''.join(ans[::-1]))
	return

def examG():

	def topological_sort(n, outs, ins):
		q = deque((v1 for v1 in range(n) if ins[v1] == 0))
		res = []
		while q:
			v1 = q.popleft()
			res.append(v1)
			for v2 in outs[v1]:
				ins[v2] -= 1
				if ins[v2] == 0:
					q.append(v2)
		return res
	(N, M) = LI()
	V = [[] for _ in range(N)]
	start = [0] * N
	for _ in range(M):
		(x, y) = LI()
		x -= 1
		y -= 1
		V[x].append(y)
		start[y] += 1
	Order = topological_sort(N, V, start)
	dp = [0] * N
	for i in Order:
		for v in V[i]:
			dp[v] = max(dp[v], dp[i] + 1)
	ans = max(dp)
	print(ans)
	return

def examH():
	(H, W) = LI()
	A = [SI() for _ in range(H)]
	dp = [[0] * W for _ in range(H)]
	dp[0][0] = 1
	for i in range(H):
		for j in range(W):
			if A[i][j] == '#':
				continue
			dp[i][j] %= mod
			if i + 1 < H and dp[i + 1][j] != '#':
				dp[i + 1][j] += dp[i][j]
			if j + 1 < W and dp[i][j + 1] != '#':
				dp[i][j + 1] += dp[i][j]
	ans = dp[-1][-1]
	print(ans)
	return

def examI():
	N = I()
	P = LFI()
	dp = [[0] * (N + 1) for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(N):
		for j in range(i + 1):
			dp[i + 1][j + 1] += dp[i][j] * P[i]
			dp[i + 1][j] += dp[i][j] * (1 - P[i])
	ans = 0
	for v in dp[N][1 + N // 2:]:
		ans += v
	print(ans)
	return

def examJ():
	N = I()
	A = LI()
	dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
	S = Counter(A)
	print(S)
	dp[S[1]][S[2]][S[3]] = 0
	que = deque()
	que.append((S[1], S[2], S[3]))
	used = defaultdict(set)
	while que:
		(n1, n2, n3) = que.popleft()
		if used[n1, n2, n3]:
			continue
		used[n1, n2, n3] = True
		now = n1 + n2 + n3
		if n1 > 0:
			dp[n1 - 1][n2][n3] += dp[n1][n2][n3] + N / now * n1 / now
			que.append((n1 - 1, n2, n3))
		if n2 > 0:
			dp[n1 + 1][n2 - 1][n3] += dp[n1][n2][n3] + N / now * n2 / now
			que.append((n1 + 1, n2 - 1, n3))
		if n3 > 0:
			dp[n1][n2 + 1][n3 - 1] += dp[n1][n2][n3] + N / now * n3 / now
			que.append((n1, n2 + 1, n3 - 1))
	ans = dp[0][0][0]
	print(ans)
	return

def examK():
	(N, K) = LI()
	A = LI()
	dp = [-1] * (K + 1)
	for i in range(1, K + 1):
		flag = False
		for a in A:
			if a > i:
				break
			if dp[i - a] == -1:
				flag = True
				break
		if flag:
			dp[i] = 1
	ans = dp[K]
	if ans == 1:
		print('First')
	else:
		print('Second')
	return

def examM():
	(N, K) = LI()
	A = LI()
	dp = [[0] * (K + 1) for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(N):
		cum = [0] * (K + 1)
		cum[0] = dp[i][0]
		for c in range(K):
			cum[c + 1] = cum[c] + dp[i][c + 1]
		for j in range(K + 1):
			if j <= A[i]:
				dp[i + 1][j] = cum[j]
			else:
				dp[i + 1][j] = cum[j] - cum[j - A[i] - 1]
			dp[i + 1][j] %= mod
	ans = dp[N][K] % mod
	print(ans)
	return

def examO():
	N = I()
	A = [LI() for _ in range(N)]
	loop = 2 ** N
	dp = [[0] * loop for _ in range(N + 1)]
	dp[0][0] = 1
	for mask in range(loop):
		cur = 0
		for j in range(N):
			if mask & 1 << j == 1 << j:
				cur += 1
		for i in range(N):
			if mask & 1 << i == 0 and A[i][cur] == 1:
				dp[cur + 1][mask | 1 << i] += dp[cur][mask]
				dp[cur + 1][mask | 1 << i] %= mod
	ans = dp[N][loop - 1]
	print(ans)
	return

def examP():

	def dfs_dp(n, s, fords, visited):
		W = 1
		B = 1
		visited[s] = True
		for v in fords[s]:
			if visited[v]:
				continue
			cur = dfs_dp(n, v, fords, visited)
			W *= sum(cur)
			B *= cur[0]
			W %= mod
			B %= mod
		return (W, B)
	N = I()
	V = [[] for _ in range(N)]
	for _ in range(N - 1):
		(x, y) = LI()
		x -= 1
		y -= 1
		V[x].append(y)
		V[y].append(x)
	visited = [False] * N
	ans = dfs_dp(N, 0, V, visited)
	print(sum(ans) % mod)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LFI():
	return list(map(float, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 6)
examO()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
n = int(input())
A = tuple((tuple(map(int, input().split())) for _ in range(n)))
dp = [[-1] * (1 << n) for _ in range(n + 1)]

def f(i, k):
	if i == n:
		return 1
	if dp[i][k] != -1:
		return dp[i][k]
	res = 0
	for j in range(n):
		if A[i][j] and k >> j & 1:
			res += f(i + 1, k ^ 1 << j)
			res %= mod
	dp[i][k] = res
	return res
ans = f(0, (1 << n) - 1)
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	a = [LI() for _ in range(n)]
	m = 2 ** n
	s = [[0] * m for _ in range(n + 1)]
	s[0][0] = 1
	ii = [2 ** i for i in range(n)]
	for i in range(n):
		t = s[i + 1]
		u = s[i]
		b = [ii[c] for c in range(n) if a[i][c]]
		for k in range(m):
			v = u[k]
			v = v % mod
			if v < 1:
				continue
			for j in b:
				if not j & k:
					t[k | j] += v
	return s[-1][-1] % mod
print(main())


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
dp = [[0] * pow(2, n) for _ in range(n + 1)]
dp[0][0] = 1
M = 10 ** 9 + 7
from itertools import combinations
for i in range(1, n + 1):
	for c in combinations(range(n), i):
		b = 0
		for item in c:
			b += 1 << item
		for item in c:
			if a[i - 1][item]:
				dp[i][b] += dp[i - 1][b - (1 << item)]
				dp[i][b] %= M
print(dp[n][pow(2, n) - 1])


P = 10 ** 9 + 7
N = int(input())
X = [input()[::2] for i in range(N)]
Y = [-1] * (1 << N)

def calc(x, n):
	if Y[x] >= 0:
		return Y[x]
	if n < 0:
		return 1
	ret = 0
	for j in range(N):
		if x & 1 << j and X[n][j] == '1':
			ret += calc(x - (1 << j), n - 1)
			ret %= P
	Y[x] = ret
	return ret
print(calc((1 << N) - 1, N - 1))


def resolve():
	MOD = 10 ** 9 + 7
	N = int(input())
	AB = [list(map(int, input().split())) for _ in range(N)]
	dp = [[0] * (1 << N) for _ in range(N + 1)]
	dp[0][0] = 1
	for i in range(N):
		for bit in range(1 << N):
			if not dp[i][bit]:
				continue
			for k in range(N):
				if AB[i][k] == 1 and bit >> k & 1 == 0:
					dp[i + 1][bit ^ 1 << k] += dp[i][bit]
					dp[i + 1][bit ^ 1 << k] %= MOD
	print(dp[N][(1 << N) - 1])
resolve()


import sys
import math
stdin = sys.stdin

def ni():
	return int(ns())

def na():
	return list(map(int, stdin.readline().split()))

def naa(N):
	return [na() for _ in range(N)]

def ns():
	return stdin.readline().rstrip()
N = ni()
a_array = naa(N)
mod = 10 ** 9 + 7
ans = [-1] * 2 ** N

def solve(n, c):
	if ans[n] != -1:
		return ans[n]
	ans[n] = 0
	if c == N - 1:
		ans[n] = a_array[c][int(math.log2(n))]
		return ans[n]
	for i in range(N):
		if a_array[c][i] == 0 or n & 1 << i == 0:
			continue
		ans[n] = (ans[n] + solve(n - (1 << i), c + 1)) % mod
	return ans[n]
print(solve(2 ** N - 1, 0))


mod = 10 ** 9 + 7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
DP = [0] * (1 << n)
DP[0] = 1
pow2 = [1 << i for i in range(n)]
cnt = [0] * (1 << n)
for i in range(1 << n - 1):
	cnt[2 * i] = cnt[i]
	cnt[2 * i + 1] = cnt[i] + 1
for state in range(1, 1 << n):
	k = cnt[state]
	for j in range(n):
		if a[k - 1][j] and state >> j & 1:
			DP[state] += DP[state ^ pow2[j]]
	DP[state] %= mod
print(DP[-1])


n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10 ** 9 + 7
DP = [-1 for s in range(1 << n)]
DP[0] = 1

def dp(s, l):
	if DP[s] != -1:
		return DP[s]
	tmp = 0
	for i in range(n):
		if s & 1 << i and A[l - 1][i]:
			tmp += dp(s & ~(1 << i), l - 1)
	DP[s] = tmp % p
	return DP[s]
print(dp((1 << n) - 1, n))


MOD = int(1000000000.0 + 7)
n = int(input())
can = []
for _ in range(n):
	can.append([int(c) for c in input().split()])
dp = [0] * 2 ** n
dp[0] = 1
for mask in range(2 ** n - 1):
	a = bin(mask).count('1')
	for b in range(n):
		if can[a][b] and (not mask & 1 << b):
			m2 = mask ^ 1 << b
			dp[m2] = dp[m2] + dp[mask]
			if dp[m2] > MOD:
				dp[m2] -= MOD
print(dp[2 ** n - 1])


import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1
for t in range(N):
	for c in combi([x for x in range(N)], t):
		x = 0
		table = [0] * N
		for i in c:
			x += 1 << i
			table[i] = 1
		for i in range(N):
			if table[i]:
				continue
			if a[t][i]:
				tt = 1 << i
				dp[x + tt] += dp[x]
				dp[x + tt] %= mod
print(dp[-1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
N = I()
data = ILL(N)
dp = [[0 for b in range(1 << N)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for b in range(1 << N):
		if dp[i][b]:
			for j in range(N):
				if data[i][j] and b >> j & 1 == 0:
					dp[i + 1][b + (1 << j)] += dp[i][b]
					dp[i + 1][b + (1 << j)] %= MOD
print(dp[-1][-1])


def main():
	import sys
	input = sys.stdin.readline
	n = int(input())
	A = [list(map(int, input().split())) for i in range(n)]
	mod = 10 ** 9 + 7
	dp = [0] * (1 << n)
	dp[0] = 1
	for s in range(1 << n):
		i = format(s, 'b').count('1')
		for j in range(n):
			if s >> j & 1 and A[i - 1][j] == 1:
				dp[s] += dp[s ^ 1 << j]
				dp[s] %= mod
	print(dp[-1])
main()


from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math
setrecursionlimit(20000)
rl = lambda : stdin.readline()
rll = lambda : stdin.readline().split()
rli = lambda : map(int, stdin.readline().split())
rlf = lambda : map(float, stdin.readline().split())
(INF, NINF) = (float('inf'), float('-inf'))

def main():
	MOD = 10 ** 9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)
	popcount = lambda x: bin(x).count('1')
	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n) - 1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and (not mask & 1 << cand):
				nmask = mask ^ 1 << cand
				dp[nmask] += dp[mask] % MOD
				dp[nmask] %= MOD
	print(dp[-1])
	stdout.close()
main()


import sys
input = sys.stdin.buffer.readline

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * pow(2, n)
dp[0] = 1
saidai = pow(2, n)
bitcnt = [0] * (saidai + 1)
for s in range(saidai):
	i = popcnt(s)
	for j in range(n):
		if s >> j & 1 == 0:
			if A[i][j] == 1:
				ns = s | 1 << j
				dp[ns] += dp[s]
				dp[ns] %= mod
print(dp[saidai - 1])


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input())
A = [tuple(map(int, input().split())) for _ in range(n)]
DP = [-1] * (1 << n)
DP[(1 << n) - 1] = 1

def dfs(s, m):
	if DP[s] != -1:
		return DP[s]
	tmp = 0
	for i in range(n):
		if s >> i & 1 == 0 and A[m][i] == 1:
			tmp += dfs(s + (1 << i), m + 1)
	DP[s] = tmp % mod
	return DP[s]
print(dfs(0, 0))


from itertools import groupby, accumulate, product, permutations, combinations

def solve():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	mod = 10 ** 9 + 7
	dp = [[0] * (1 << N) for _ in range(N + 1)]
	dp[N][-1] = 1
	for i in range(N - 1, -1, -1):
		for com in combinations(range(N), i):
			S = 0
			for k in com:
				S += 1 << k
			for j in range(N):
				if not S >> j & 1:
					if A[i][j] == 1:
						dp[i][S] += dp[i + 1][S + (1 << j)]
						dp[i][S] %= mod
	return dp[0][0]
print(solve())


n = int(input())
a = [list(map(int, list(input().split()))) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * 2 ** n
dp[0] = 1
bitcnt = [0] * 2 ** n

def who(s):
	ans = []
	i = 0
	while s > 0:
		if s % 2:
			ans.append(i)
		i += 1
		s = s >> 1
	return ans
for i in range(1, 2 ** n):
	bitcnt[i] = bitcnt[i >> 1] + i % 2
	for l in who(i):
		dp[i] += dp[i - 2 ** l] * a[bitcnt[i] - 1][l]
		dp[i] %= mod
print(dp[2 ** n - 1])


mod = 10 ** 9 + 7
n = int(input())
match_list = []
for i in range(n):
	match_list.append(list(map(int, input().split())))
c = [0]
for i in range(n):
	c += [j + 1 for j in c]
dp = [0] * (1 << n)
dp[0] = 1
for i in range((1 << n) - 1):
	for j in range(n):
		if match_list[c[i]][j]:
			dp[1 << j ^ i] = (dp[1 << j ^ i] + dp[i]) % mod
print(dp[-1])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
dp = [[0] * pow(2, n) for _ in range(n + 1)]
dp[0][0] = 1
M = 10 ** 9 + 7
for i in range(1, n + 1):
	comb = (1 << i) - 1
	while comb < 1 << n:
		for j in range(n):
			if comb >> j and a[i - 1][j]:
				dp[i][comb] += dp[i - 1][comb - (1 << j)]
				dp[i][comb] %= M
		x = comb & -comb
		y = comb + x
		comb = (comb & ~y) // x >> 1 | y
print(dp[n][pow(2, n) - 1])


mod = 10 ** 9 + 7
N = int(input())
A = [int(input().replace(' ', ''), 2) for _ in range(N)]
dp = [0] * 2 ** N
dp[0] = 1
for state in range(2 ** N - 1):
	a = A[bin(state).count('1')] & ~state
	for j in range(N):
		if a & 1 << j:
			dp[state | 1 << j] += dp[state]
print(dp[-1] % mod)


N = int(input())
A = [0] * N
for i in range(N):
	A[i] = list(map(int, input().split()))
from itertools import groupby, accumulate, product, permutations, combinations

def solve(N, A):
	mod = 10 ** 9 + 7
	dp = [0] * (1 << N)
	dp[0] = 1
	for i in range(1, N + 1):
		for com in combinations(range(N), i):
			s = 0
			for c in com:
				s += 1 << c
			for rem in com:
				dp[s] += dp[s - (1 << rem)] * A[i - 1][rem]
				dp[s] %= mod
	ans = dp[-1]
	return ans
print(solve(N, A))


n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
MOD = 10 ** 9 + 7
size = 1 << n
dp = [0] * size
dp[0] = 1
for i in range(size - 1):
	num = bin(i).count('1')
	for c in range(n):
		new = 1 << c ^ i
		if A[num][c] and new != i:
			dp[new] += dp[i]
			if dp[new] > MOD:
				dp[new] -= MOD
print(dp[-1])


MOD = 10 ** 9 + 7
N = int(input())
As = [int(input().replace(' ', ''), 2) for _ in range(N)]
patWsList = [[] for _ in range(N + 1)]
for patW in range(2 ** N):
	num1 = sum([patW >> i & 1 for i in range(N)])
	patWsList[num1].append(patW)
dp = [0] * 2 ** N
dp[-1] = 1
for (iM, (A, patWs)) in enumerate(zip(As, reversed(patWsList))):
	for patW in patWs:
		A2 = A & patW
		dpNow = dp[patW]
		for iW in range(N):
			if A2 & 1 << iW:
				dp[patW ^ 1 << iW] += dpNow
				dp[patW ^ 1 << iW] %= MOD
print(dp[0])


N = int(input())
to = [[] for _ in range(N)]
for i in range(N):
	a = list(map(int, input().split()))
	for j in range(N):
		if a[j] == 1:
			to[i].append(j)
dp = [0] * (1 << N)
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range((1 << N) - 1):
	c = 0
	for j in range(N):
		if i >> j & 1:
			c += 1
	for j in to[c]:
		if not i >> j & 1:
			dp[i | 1 << j] += dp[i]
			dp[i | 1 << j] %= MOD
print(dp[-1])


N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * 2 ** N
dp[0] = 1
POPCOUNT_TABLE16 = [0] * 2 ** 16
for index in range(len(POPCOUNT_TABLE16)):
	POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt(v):
	return POPCOUNT_TABLE16[v & 65535] + POPCOUNT_TABLE16[v >> 16 & 65535] + POPCOUNT_TABLE16[v >> 32 & 65535] + POPCOUNT_TABLE16[v >> 48]
for s in range(1, 2 ** N):
	i = popcnt(s)
	cnt = 0
	for j in range(N):
		if A[i - 1][j] == 1 and s & 1 << j:
			cnt += dp[s ^ 1 << j] % mod
	dp[s] = cnt % mod
print(dp[-1] % mod)


def solve():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	mod = 10 ** 9 + 7
	dp = [[0] * (1 << N) for _ in range(N + 1)]
	dp[N][-1] = 1
	for S in range((1 << N) - 1, -1, -1):
		i = sum([1 & S >> k for k in range(N)])
		for j in range(N):
			if not S >> j & 1:
				if A[i][j] == 1:
					dp[i][S] += dp[i + 1][S + (1 << j)]
					dp[i][S] %= mod
	return dp[0][0]
print(solve())


def main():
	N = int(input())
	a = [list(map(int, input().split())) for i in range(N)]

	def popcount(x):
		x = x - (x >> 1 & 6148914691236517205)
		x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
		x = x + (x >> 4) & 1085102592571150095
		x = x + (x >> 8)
		x = x + (x >> 16)
		x = x + (x >> 32)
		return x & 127
	dp = [[0] * (1 << N) for i in range(N + 1)]
	dp[0][0] = 1
	mod = 10 ** 9 + 7
	for j in range(1, 1 << N):
		i = popcount(j)
		DP = dp[i]
		prev = dp[i - 1]
		for k in range(N):
			if (j >> k) % 2 == 1:
				if a[i - 1][k] == 1:
					DP[j] += prev[j ^ 1 << k]
					DP[j] %= mod
	print(dp[-1][(1 << N) - 1])
main()


import itertools
mod = 10 ** 9 + 7
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 2 ** n for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for bit in range(2 ** n):
		if dp[i][bit] != 0:
			for j in range(n):
				if bit & 2 ** j == 0 and arr[i][j] == 1:
					dp[i + 1][bit ^ 2 ** j] += dp[i][bit]
					dp[i + 1][bit ^ 2 ** j] %= mod
print(dp[n][2 ** n - 1])


mod = 1000000007
n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
for i in range(n):
	compatibilities = [1 << i for (i, v) in enumerate(input().split()) if v == '1']
	nxt = set()
	for k in curr:
		p = dp[k] % mod
		for c in compatibilities:
			if k & c:
				continue
			dp[k | c] += p
			nxt.add(k | c)
	curr = nxt
print(dp[(1 << n) - 1] % mod)


n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(1, 1 << n):
	cnt = 0
	for j in range(n + 1):
		cnt += i >> j & 1
	for j in range(n):
		if i >> j & 1 == 0:
			continue
		dp[i] += dp[i - (1 << j)] * A[cnt - 1][j]
		dp[i] %= mod
print(dp[-1] % mod)


import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
	if dp[group] != -1:
		return dp[group]
	res = 0
	for i in range(N):
		if group >> i & 1 == 0 and A[count][i] == 1:
			res += dfs(group + (1 << i), count + 1)
	dp[group] = res % MOD
	return dp[group]
tmp = dfs(0, 0)
print(tmp)


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1
for i in range(1, 1 << N):
	cnt = bin(i).count('1')
	for j in range(N):
		if i >> j & 1 == 0:
			continue
		dp[i] += dp[i - (1 << j)] * A[cnt - 1][j]
		dp[i] %= MOD
print(dp[-1])


def solve():
	MOD = 10 ** 9 + 7
	N = int(input())
	Ass = [tuple(map(int, input().split())) for _ in range(N)]
	Sss = [[] for _ in range(N + 1)]
	for S in range(1 << N):
		num1 = bin(S).count('1')
		Sss[num1].append(S)
	dp = [0] * (1 << N)
	dp[0] = 1
	for (iM, Ss) in enumerate(Sss[:-1]):
		for S in Ss:
			dp[S] %= MOD
			for iW in range(N):
				if S & 1 << iW == 0 and Ass[iM][iW]:
					S2 = S | 1 << iW
					dp[S2] += dp[S]
	print(dp[-1] % MOD)
solve()


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10000000)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate
	from bisect import bisect_left, bisect_right
	import heapq
	from math import floor, ceil
	mod = 10 ** 9 + 7
	N = int(input())
	a = [list(map(int, input().split())) for _ in range(N)]
	dp = [-1] * (1 << N)
	dp[-1] = 1

	def dfs(s, num):
		if dp[s] != -1:
			return dp[s]
		res = 0
		for i in range(N):
			if s >> i & 1 == 0 and a[num][i] == 1:
				res += dfs(s + (1 << i), num + 1)
		dp[s] = res % mod
		return dp[s]
	print(dfs(0, 0))
main()


from collections import deque
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
cs = [0] * (1 << N)
used = [0] * (1 << N)
s = (1 << N) - 1
que = deque([(s, 0)])
cs[s] = 1
used[s] = 1
while que:
	(state, c) = que.popleft()
	v = cs[state] % MOD
	for i in range(N):
		if state & 1 << i and A[c][i]:
			n_state = state ^ 1 << i
			cs[n_state] += v
			if not used[n_state] and c + 1 < N:
				que.append((n_state, c + 1))
				used[n_state] = 1
print(cs[0] % MOD)


mod = 10 ** 9 + 7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
for s in range(1, 1 << N):
	women = []
	for i in range(N):
		if 1 << i & s:
			women.append(i)
	m = len(women) - 1
	for w in women:
		if a[m][w] == 1:
			dp[s] += dp[s ^ 1 << w]
			dp[s] %= mod
print(dp[-1])


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter, defaultdict
from operator import mul
import copy
import heapq
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
import bisect
import statistics
mod = 10 ** 9 + 7

def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127

def bit(S, j):
	return S >> j & 1
N = int(input())
a = [[] for i in range(N)]
for i in range(N):
	a[i] = list(map(int, input().split()))
dp = [0 for i in range(1 << N)]
dp[0] = 1
for S in range(1, 1 << N):
	i = popcount(S)
	for j in range(N):
		if bit(S, j) == 1 and a[i - 1][j] == 1:
			dp[S] = (dp[S] + dp[S ^ 1 << j]) % mod
print(dp[(1 << N) - 1] % mod)


def main():
	n = int(input())
	A = [list(map(int, input().split())) for i in range(n)]
	p = 10 ** 9 + 7
	DP = [0 for s in range(1 << n)]
	DP[0] = 1
	for s in range(1, 1 << n):
		l = bin(s).count('1')
		for i in range(n):
			if (1 << i & s) * A[l - 1][i]:
				DP[s] += DP[~(1 << i) & s]
	print(DP[(1 << n) - 1] % p)
main()


def main():
	N = int(input())
	adj = []
	for i in range(N):
		adj.append(list(map(int, input().split())))
	mod = 10 ** 9 + 7
	state_list = [[] for _ in range(N + 1)]
	for state in range(2 ** N):
		one_num = 0
		for j in range(N):
			if state >> j & 1:
				one_num += 1
		state_list[one_num].append(state)
	dp = [0] * 2 ** N
	dp[0] = 1
	for i in range(N):
		for j in range(N):
			if adj[i][j]:
				for state in state_list[i]:
					state_new = state | 2 ** j
					if state != state_new:
						dp[state_new] = (dp[state_new] + dp[state]) % mod
	print(dp[-1])
main()


def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	N = I()
	a = [[] for _ in range(N)]
	for i in range(N):
		a[i] = LI()
	M = pow(2, N)
	dp = [0] * M
	dp[0] = 1

	def bit_cnt(N):
		B = bin(N)
		return B.count('1')
	for S in range(M - 1):
		if dp[S] == 0:
			continue
		man = bit_cnt(S)
		for i in range(N):
			if S >> i & 1 == 0:
				if a[man][i] == 1:
					dp[S + (1 << i)] += dp[S]
					dp[S + (1 << i)] %= mod
	print(dp[-1])
main()


def resolve():
	MOD = 10 ** 9 + 7
	N = int(input())
	AB = [list(map(int, input().split())) for _ in range(N)]
	dp = [0] * (1 << N)
	dp[0] = 1
	bitcount = [0]
	for _ in range(N):
		bitcount += [i + 1 for i in bitcount]
	for bit in range(1 << N):
		i = bitcount[bit]
		for j in range(N):
			if bit >> j & 1 == 0 and AB[i - 1][j] == 1:
				dp[bit ^ 1 << j] += dp[bit]
		dp[bit] %= MOD
	print(dp[-1])
resolve()


def popcount(x):
	c = 0
	while x > 0:
		if x & 1:
			c += 1
		x = x >> 1
	return c

def f(A):
	MOD = 10 ** 9 + 7
	n = len(A)
	dp = [0] * (1 << n)
	dp[0] = 1
	for mask in range((1 << n) - 1):
		a = popcount(mask)
		for b in range(n):
			if A[a][b] and (not mask & 1 << b):
				m2 = mask ^ 1 << b
				dp[m2] += dp[mask]
				if dp[m2] > MOD:
					dp[m2] -= MOD
	return dp[(1 << n) - 1]
assert f([[0, 1, 1], [1, 0, 1], [1, 1, 1]]) == 3
n = int(input())
A = []
for _ in range(n):
	R = list(map(int, input().split()))
	A.append(R)
ans = f(A)
print(ans)


MOD = 1000000007
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(1 << N)]
dp[0] = 1
for i in range(1, 1 << N):
	k = 0
	for j in range(N):
		if i >> j & 1:
			k += 1
	for j in range(N):
		if i >> j & 1 and A[k - 1][j]:
			dp[i] += dp[i ^ 1 << j]
			dp[i] %= MOD
print(dp[-1])


def edu_dp_d_matching():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(list(map(int, input().split())))
	dp = [[0] * (1 << n) for _ in range(n)]
	for i in range(n):
		if a[0][i] == 1:
			dp[0][1 << i] = 1
	for i in range(1, n):
		for k in range(1 << n):
			if dp[i - 1][k] == 0:
				continue
			for j in range(n):
				if a[i][j] == 0 or k & 1 << j != 0:
					continue
				dp[i][k | 1 << j] += dp[i - 1][k]
	print(dp[-1][-1] % (pow(10, 9) + 7))
edu_dp_d_matching()


def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	N = I()
	a = [[] for _ in range(N)]
	for i in range(N):
		a[i] = LI()
	M = pow(2, N)
	dp = [0] * M
	dp[0] = 1
	p = [1] * (N + 3)
	for i in range(N + 2):
		p[i + 1] = p[i] * 2

	def make(L):
		res = 0
		for i in range(len(L)):
			res += p[L[i]]
		return res
	import itertools
	for man in range(N):
		for ite in itertools.combinations(range(N), man):
			S = make(ite)
			if dp[S] == 0:
				continue
			for i in range(N):
				if S >> i & 1 == 0:
					if a[man][i] == 1:
						dp[S + (1 << i)] += dp[S]
						dp[S + (1 << i)] %= mod
	print(dp[-1])
main()


inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
R = 1000000007

def dfs(x, y):
	if x == n:
		return 1
	if dp[y] > -1:
		return dp[y]
	sum = 0
	for j in range(n):
		b = 1 << j
		if a[x][j] == 1 and y & b == 0:
			sum += dfs(x + 1, y | b)
			if sum > R:
				sum -= R
	dp[y] = sum
	return sum
n = inn()
a = [0 for i in range(n)]
for i in range(n):
	a[i] = inl()
dp = [-1] * 2 ** n
print(dfs(0, 0))


def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127
f = popcount
a = []
n = int(input())
for _ in range(n):
	a.append(tuple(map(int, input().split())))
S = 1 << n
dp = [0] * S
dp[0] = 1
for s in range(1, S):
	i = f(s)
	for j in range(n):
		if s >> j & 1:
			if a[i - 1][j]:
				dp[s] += dp[s - (1 << j)]
		else:
			dp[s] %= 10 ** 9 + 7
			continue
print(dp[S - 1] % (10 ** 9 + 7))


def countSetBits(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count
N = 10 ** 9 + 7
n = int(input())
ar = [list(map(int, input().split())) for _ in range(n)]
total = 1 << n
bits = [[] for _ in range(n + 1)]
dp = [[0] * (total + 5) for j in range(n + 5)]
for i in range(n):
	if ar[0][i] == 1:
		dp[0][1 << n - 1 - i] = 1
for j in range(total):
	i = countSetBits(j) - 1
	for k in range(0, n):
		if ar[i][n - k - 1] == 1 and j & 1 << k:
			dp[i][j] = (dp[i][j] + dp[i - 1][j & ~(1 << k)]) % N
print(dp[n - 1][total - 1])


import sys
input = sys.stdin.readline
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
MOD = 10 ** 9 + 7
_ALL = 1 << n
dp = [0] * _ALL
dp[0] = 1
for m in range(1, n + 1):
	a = 2 ** m - 1
	while a < _ALL:
		ans = 0
		for c in range(n):
			if 1 << c & a and A[m - 1][c]:
				ans += dp[a ^ 1 << c]
				ans %= MOD
		dp[a] = ans
		x = a & -a
		y = a + x
		a = (a & ~y) // x >> 1 | y
print(dp[2 ** n - 1])


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
dp = [[0] * (1 << n) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	bit_state = (1 << i) - 1
	if bit_state == 0:
		for j in range(n):
			if not bit_state & 1 << j and a[i][j] == 1:
				dp[i + 1][bit_state | 1 << j] += dp[i][bit_state]
				dp[i + 1][bit_state | 1 << j] %= MOD
		continue
	while bit_state < 1 << n:
		for j in range(n):
			if not bit_state & 1 << j and a[i][j] == 1:
				dp[i + 1][bit_state | 1 << j] += dp[i][bit_state]
				dp[i + 1][bit_state | 1 << j] %= MOD
		x = bit_state & -bit_state
		y = bit_state + x
		bit_state = (bit_state & ~y) // x >> 1 | y
print(dp[n][(1 << n) - 1])


n = int(input())
g = []
for i in range(n):
	g.append(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [0] * 2 ** n
dp[0] = 1
for i in range(1, 2 ** n):
	e = bin(i)[2:]
	y = e.count('1')
	for j in range(len(e)):
		if e[-j - 1] == '1':
			if g[y - 1][j]:
				dp[i] += dp[i - 2 ** j]
				dp[i] %= mod
print(dp[-1] % mod)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(rows_number)]

def main():
	md = 10 ** 9 + 7
	n = int(input())
	aa = LLI(n)
	lov = [[] for _ in range(n)]
	for (i, ar) in enumerate(aa):
		for (j, a) in enumerate(ar):
			if a:
				lov[i].append(j)
	dp = [0] * (1 << n)
	dp[0] = 1
	for s in range((1 << n) - 1):
		pre = dp[s]
		if pre == 0:
			continue
		i = bin(s).count('1')
		for j in lov[i]:
			if s >> j & 1:
				continue
			ns = s | 1 << j
			dp[ns] = (dp[ns] + pre) % md
	print(dp[-1])
main()


N = int(input())
a = [[int(i) for i in input().split()] for _ in range(N)]
MOD = 10 ** 9 + 7
dp = [0 for _ in range(1 << N)]
dp[0] = 1
for S in range(1, 1 << N):
	i = bin(S).count('1')
	for x in range(N):
		if S >> x & 1 and a[i - 1][x] == 1:
			dp[S] = (dp[S] + dp[S ^ 1 << x]) % MOD
print(dp[-1])


import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : map(int, sys.stdin.readline().split())
na = lambda : list(map(int, sys.stdin.readline().split()))

def main():
	n = ni()
	table = [na() for _ in range(n)]
	dp = [0 for _ in range(2 ** n)]
	dp[2 ** n - 1] = 1
	for i in range(2 ** n - 1, 0, -1):
		j = n - format(i, 'b').count('1')
		for (j, val) in enumerate(table[j]):
			if val:
				if i & 1 << j:
					tmp = i ^ 1 << j
					dp[tmp] += dp[i]
					dp[tmp] %= MOD
	print(dp[0])
main()


n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for i in range(n):
	compatibilities = [1 << i for (i, v) in enumerate(input().split()) if v == '1']
	nxt = set()
	for k in curr:
		p = dp[k] % MOD
		for c in compatibilities:
			if k & c:
				continue
			dp[k | c] += p
			nxt.add(k | c)
	curr = nxt
print(dp[(1 << n) - 1] % MOD)


import sys

class OMatching:

	def solve(self):
		from collections import defaultdict

		def numberOfSetBits(i):
			i = i - (i >> 1 & 1431655765)
			i = (i & 858993459) + (i >> 2 & 858993459)
			return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
		MOD = 10 ** 9 + 7
		n = int(input())
		a = []
		for i in range(n):
			a.append([int(_) for _ in input().split()])
		dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		by_1 = defaultdict(list)
		for j in range(1 << n):
			by_1[numberOfSetBits(j)].append(j)
		for i in range(1, n + 1):
			for j in by_1[i - 1]:
				for k in range(n):
					if j >> k & 1 or a[i - 1][k] == 0:
						continue
					dp[i][j | 1 << k] += dp[i - 1][j]
					dp[i][j | 1 << k] %= MOD
		print(sum(dp[n]))
solver = OMatching()
input = sys.stdin.readline
solver.solve()


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [-1] * (1 << n)
dp[0] = 1

def solve(bits, i):
	if dp[bits] != -1:
		return dp[bits]
	total = 0
	for j in range(n):
		if bits & 1 << j and a[i][j]:
			total += solve(bits ^ 1 << j, i - 1)
	dp[bits] = total % mod
	return dp[bits]
print(solve((1 << n) - 1, n - 1))


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [-1] * (1 << n)
dp[0] = 1

def dfs(bit, i):
	if dp[bit] != -1:
		return dp[bit]
	else:
		tmp = 0
		for j in range(n):
			if bit & 1 << j and a[i][j]:
				tmp += dfs(bit ^ 1 << j, i + 1)
	dp[bit] = tmp % mod
	return dp[bit]
print(dfs(2 ** n - 1, 0))


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))

def b(n, k):
	return n >> k & 1
MOD = 10 ** 9 + 7
dp = [[0 for j in range(1 << n)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for S in range(1 << n):
		if dp[i][S]:
			for j in range(n):
				if b(S, j) == 0 and a[i][j] == 1:
					dp[i + 1][S ^ 1 << j] += (dp[i][S ^ 1 << j] + dp[i][S]) % MOD
					dp[i + 1][S ^ 1 << j] %= MOD
print(dp[n][-1])


N = int(input())
Match = [0] * N
mod = 10 ** 9 + 7
for i in range(N):
	A = list(map(int, input().split()))
	m = 0
	for (j, a) in enumerate(A):
		if a:
			m |= 1 << j
	Match[i] = m
DP = [0] * (1 << N)
DP[0] = 1
bit_count = [0]
for _ in range(N):
	bit_count += [x + 1 for x in bit_count]
for i in range((1 << N) - 1):
	c = bit_count[i]
	if DP[i] == 0:
		continue
	for j in range(N):
		if Match[c] >> j & 1 == 1:
			if i >> j & 1 == 0:
				DP[i | 1 << j] += DP[i]
				DP[i | 1 << j] %= mod
print(DP[-1] % mod)


mod = 10 ** 9 + 7
N = int(input())
li = [list(map(int, input().split())) for i in range(N)]
lc = [0] * (1 << N)
dp = [0] * (1 << N)
dp[0] = 1
for S in range(1, 1 << N):
	lc[S] = lc[S >> 1] + S % 2
	for i in range(N):
		if S >> i & li[lc[S] - 1][i] == 1:
			dp[S] = (dp[S] + dp[S - (1 << i)]) % mod
print(dp[(1 << N) - 1])


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
dp = [-1] * 2 ** N
dp[0] = 1

def solve(state, c):
	global dp
	if dp[state] >= 0:
		return dp[state]
	else:
		dp[state] = 0
		for i in range(N):
			if state & 1 << i and A[c - 1][i]:
				dp[state] += solve(state ^ 1 << i, c - 1)
				dp[state] %= MOD
		return dp[state]
print(solve(2 ** N - 1, N))


import sys
input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * pow(2, n)
dp[0] = 1
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
	bitcnt[s] = bitcnt[s // 2] + s % 2
	i = bitcnt[s]
	for j in range(n):
		if s >> j & 1 == 0:
			if A[i][j] == 1:
				ns = s | 1 << j
				dp[ns] += dp[s]
				dp[ns] %= mod
print(dp[pow(2, n) - 1])


def main():
	M = 10 ** 9 + 7
	(n, *a) = open(0)
	n = int(n)
	a = [list(map(int, t[::2])) for t in a]
	dp = [1] + [0] * (2 ** n - 1)
	for i in range(2 ** n - 1):
		j = bin(i).count('1')
		for k in range(n):
			to = i | 1 << k
			if to == i or not a[j][k]:
				continue
			dp[to] += dp[i]
			dp[to] %= M
	print(dp[-1])
main()


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
ALL = 1 << N
S = [0] * ALL
MOD = 10 ** 9 + 7
S[ALL - 1] = 1
for k in range(N, 0, -1):
	I = [i for i in range(N) if A[k - 1][i]]
	v = (1 << k) - 1
	while v < ALL:
		w = S[v] % MOD
		for i in I:
			if v & 1 << i:
				S[v ^ 1 << i] += w
		x = v & -v
		y = v + x
		v = (v & ~y) // x >> 1 | y
print(S[0] % MOD)


def solve(n, a):
	mod = 10 ** 9 + 7
	dp = [0] * (1 << n)
	dp[0] = 1
	for mask in range(1, 1 << n):
		man = bin(mask).count('1') - 1
		for woman in range(n):
			if mask >> woman & 1 == 1 and a[man][woman] == 1:
				dp[mask] = (dp[mask] + dp[mask & ~(1 << woman)]) % mod
	return dp[(1 << n) - 1]
n = int(input())
a = tuple((tuple(map(int, input().split())) for _ in range(n)))
print(solve(n, a))


def solve():
	MOD = 10 ** 9 + 7
	N = int(input())
	Ass = [tuple(map(int, input().split())) for _ in range(N)]
	dp = [[0] * (1 << N) for _ in range(N + 1)]
	dp[0][0] = 1
	for iM in range(N):
		for S in range(1 << N):
			if dp[iM][S]:
				dp[iM][S] %= MOD
				for iW in range(N):
					if S & 1 << iW == 0 and Ass[iM][iW]:
						S2 = S ^ 1 << iW
						dp[iM + 1][S2] += dp[iM][S]
	print(dp[-1][-1] % MOD)
solve()


N = int(input())
A = [[int(_) for _ in input().split()] for i in range(N)]
dp = [[0] * ((1 << 21) + 10) for _ in range(N + 1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
for i in range(N):
	for s in range(1 << N):
		if dp[i][s] == 0:
			continue
		for j in range(N):
			jb = 1 << j
			if not s & jb and A[i][j]:
				dp[i + 1][s | jb] += dp[i][s] % MOD
print(dp[N][(1 << N) - 1] % MOD)


def main():
	N = int(input())
	a = []
	for i in range(N):
		a.append(list(map(int, input().split())))
	mod = 10 ** 9 + 7
	dp = [0] * 2 ** N
	dp[0] = 1
	for i in range(1, 2 ** N):
		m = [j for j in range(N) if i >> j & 1 == 1]
		for j in m:
			dp[i] += dp[i - 2 ** j] * a[len(m) - 1][j]
		dp[i] %= mod
	print(dp[-1])
main()


mod = 10 ** 9 + 7
n = int(input())
A = []
for i in range(n):
	A.append(list(map(int, input().split())))
memo = [-1] * (1 << n)
memo[0] = 1

def dfs(state, c):
	if memo[state] != -1:
		return memo[state]
	r = 0
	for i in range(n):
		if state & 1 << i and A[c][i]:
			r += dfs(state ^ 1 << i, c + 1)
			r %= mod
	memo[state] = r
	return r
print(dfs((1 << n) - 1, 0))


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
memo = [-1] * 2 ** n
memo[0] = 1

def dfs(state, c):
	if memo[state] != -1:
		return memo[state]
	r = 0
	for i in range(n):
		if state & 1 << i and A[c][i]:
			r += dfs(state ^ 1 << i, c + 1)
	memo[state] = r % mod
	return r
print(dfs(2 ** n - 1, 0) % mod)


def calcdp(i, s):
	global dp, MOD, N, A
	if dp[i][s] != -1:
		return dp[i][s]
	r = 0
	for j in range(N):
		if A[i - 1][j] and s & 1 << j:
			r += calcdp(i - 1, s ^ 1 << j)
	dp[i][s] = r = r % MOD
	return r
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
MOD = 10 ** 9 + 7
dp = [[-1] * 2 ** N for _ in range(N + 1)]
dp[0][0] = 1
print(calcdp(N, 2 ** N - 1))


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = pow(10, 9) + 7
dp = [0] * (1 << n)
dp[0] = 1
for i in range(1 << n):
	cnt = 0
	v = []
	for j in range(n):
		if i >> j & 1:
			cnt += 1
			v.append(j)
	for j in v:
		dp[i] += dp[i ^ 1 << j] * a[j][cnt - 1]
		dp[i] %= mod
print(dp[-1])


MOD = 10 ** 9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N + 1)]
for s in range(1 << N):
	temp = 0
	for n in range(N):
		if s & 1 << n:
			temp += 1
	cands[temp].append(s)
for (i, a) in enumerate(A):
	for j in [k for (k, v) in enumerate(a) if v == 1]:
		bit = bits[j]
		for s in cands[i]:
			if s & bit == 0:
				new_s = s | bit
				dp[new_s] += dp[s]
				dp[new_s] %= MOD
print(dp[-1])


def main():
	MOD = 10 ** 9 + 7
	N = int(input())
	A = [list(map(int, input().split(' '))) for _ in range(N)]
	dp = [0 for _ in range(1 << N)]
	dp[0] = 1
	for s in range(1, 1 << N):
		women_list = [w for w in range(N) if s >> w & 1 == 1]
		man = len(women_list) - 1
		val = 0
		for woman in women_list:
			val += A[man][woman] * dp[s - (1 << woman)]
		val %= MOD
		dp[s] += val
	print(dp[(1 << N) - 1])
main()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10 ** 9 + 7
dp = [0] * 2 ** n
dp[0] = 1
for i in range(1, 2 ** n):
	x = bin(i)[2:]
	y = x.count('1')
	for j in range(len(x)):
		if x[-j - 1] == '1':
			if a[y - 1][j] == 1:
				dp[i] += dp[i - 2 ** j]
				dp[i] %= mod
print(dp[-1])


import sys
input = sys.stdin.readline
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10 ** 9 + 7
dp = [0] * 2 ** N
que = [0]
data = [[] for i in range(N + 1)]
for i in range(2 ** N):
	cnt = 0
	for j in range(N):
		if i & 1 << j == 0:
			continue
		cnt += 1
	data[cnt].append(i)
for j in range(N):
	if A[0][j] == 1:
		num = 1 << j
		dp[num] += 1
for i in range(N):
	for j in range(N):
		if A[i][j] == 1:
			num = 1 << j
			for u in data[i]:
				dp[u ^ num] = (dp[u ^ num] + dp[u]) % mod
print(dp[-1])


N = int(input())
a = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
M = pow(2, N)
DP = [0] * M
for i in range(N):
	DP[1 << i] = a[0][i]
for i in range(2, N + 1):
	n = (1 << i) - 1
	while n < 1 << N:
		x = n
		cnt = 0
		while x != 0:
			if x & 1 == 1:
				if a[i - 1][cnt] == 1:
					DP[n] = (DP[n] + DP[n & ~(1 << cnt)]) % MOD
			x >>= 1
			cnt += 1
		x = n & -n
		y = n + x
		n = (n & ~y) // x >> 1 | y
print(DP[-1])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7
I = [[j for j in range(N) if Ai[j]] for Ai in A]
memo = [-1] * (1 << N)
memo[0] = 1

def dfs(S, c):
	if memo[S] != -1:
		return memo[S]
	r = 0
	for i in I[c]:
		if S & 1 << i:
			r += dfs(S ^ 1 << i, c + 1)
	memo[S] = r = r % MOD
	return r
print(dfs((1 << N) - 1, 0))


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (1 << n)
bit = [0] * (1 << n)
dp[0] = 1
for i in range(1, 1 << n):
	bit[i] = bit[i // 2] + i % 2
	for j in range(n):
		if i >> j & 1:
			dp[i] += dp[i - (1 << j)] * a[bit[i] - 1][j]
			dp[i] %= mod
print(dp[-1] % mod)


import sys
input = sys.stdin.readline
bit = lambda s, j: s >> j & 1

def f(n, a):
	mod = int(1000000000.0 + 7)
	sn = 1 << n
	dp = [[0] * sn for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		dpi = dp[i]
		dpi1 = dp[i + 1]
		ai = a[i]
		for s in range(0, sn):
			if dpi[s]:
				for j in range(n):
					if bit(s, j) == 0 and ai[j]:
						s_ = s | 1 << j
						dpi1[s_] += dpi[s]
						if dpi1[s_] > mod:
							dpi1[s_] -= mod
	return dp[-1][-1]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
print(f(n, a))


import sys
MAX_INT = int(1e+16)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)

def IL():
	return list(map(int, input().split()))

def SL():
	return input().split()

def I():
	return int(sys.stdin.readline())

def S():
	return input()
N = I()
a = [IL() for _ in range(N)]
dp = [0] * (1 << N)
for i in range(N):
	dp[1 << i] = a[0][i]
for i in range(2, N + 1):
	n = (1 << i) - 1
	while n < 1 << N:
		x = n
		for j in range(N):
			if x >> j & 1:
				if a[i - 1][j] == 1:
					dp[x] += dp[x ^ 1 << j] % mod
		x = n & -n
		y = n + x
		n = (n & ~y) // x >> 1 | y
print(dp[-1] % mod)


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():
	n = II()
	a = LIR(n)
	n1 = 1 << n
	dp = [0] * n1
	dp[0] = 1
	b = [0]
	for i in range(n):
		b += [x + 1 for x in b]
	c = [1 << i for i in range(n)]
	for i in range(n1 - 1):
		p = b[i]
		ap = a[p]
		for j in range(n):
			if ap[j]:
				j1 = c[j]
				if i & j1:
					continue
				dp[i | j1] += dp[i]
	print(dp[-1] % mod)
	return
solve()


import sys

def input():
	return sys.stdin.readline().rstrip()
from itertools import product

def main():
	n = int(input())
	A = [[int(_) for _ in input().split()] for i in range(n)]
	dp = [0] * (1 << n)
	dp[0] = 1
	mod = 10 ** 9 + 7
	for s in range(1 << n):
		i = bin(s).count('1')
		for j in range(n):
			if s >> j & 1 and A[i - 1][j] == 1:
				dp[s] = (dp[s] + dp[s ^ 1 << j]) % mod
	print(dp[(1 << n) - 1])
main()


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
memo = [-1] * 2 ** N
memo[0] = 1

def dfs(bit_state, matched):
	if memo[bit_state] != -1:
		return memo[bit_state]
	r = 0
	for i in range(N):
		if bit_state & 1 << i and A[matched][i]:
			r += dfs(bit_state ^ 1 << i, matched + 1)
	r %= MOD
	memo[bit_state] = r
	return r
print(dfs(2 ** N - 1, 0))


from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math
setrecursionlimit(20000)
rl = lambda : stdin.readline()
rll = lambda : stdin.readline().split()
rli = lambda : map(int, stdin.readline().split())
rlf = lambda : map(float, stdin.readline().split())
(INF, NINF) = (float('inf'), float('-inf'))

def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127

def main():
	MOD = 10 ** 9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)
	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n) - 1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and (not mask & 1 << cand):
				nmask = mask ^ 1 << cand
				dp[nmask] += dp[mask] % MOD
				dp[nmask] %= MOD
	print(dp[-1])
	stdout.close()
main()


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
a = []
dp = [-1] * (1 << n)
dp[(1 << n) - 1] = 1
mod = 10 ** 9 + 7
for i in range(n):
	a.append(list(map(int, input().split())))

def dfs(s, cnt):
	if dp[s] != -1:
		return dp[s]
	res = 0
	for i in range(n):
		if s >> i & 1 == 0 and a[cnt][i] == 1:
			res += dfs(s + (1 << i), cnt + 1)
	dp[s] = res % mod
	return dp[s]
print(dfs(0, 0))


N = int(input())
dp = [0] * (1 << N)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for _ in range(N):
	a = [1 << i for (i, v) in enumerate(input().split()) if v == '1']
	nxt = set()
	for i in curr:
		dpi = dp[i] % MOD
		for j in a:
			if i & j:
				continue
			dp[i | j] += dpi
			nxt.add(i | j)
	curr = nxt
print(dp[(1 << N) - 1] % MOD)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
from collections import Counter
M = 10 ** 9 + 7
cur = [0] * (1 << N)
cur[0] = 1
for B in A:
	nxt = [0] * (1 << N)
	C = [1 << i for (i, v) in enumerate(B) if v == 1]
	for (s, v) in enumerate(cur):
		if v == 0:
			continue
		v %= M
		for b in C:
			if s & b != 0:
				continue
			nxt[s | b] += v
	cur = nxt
print(cur[(1 << N) - 1] % M)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
a = [LI() for _ in range(n)]
dp = [[0] * 2 ** n for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(2 ** n):
		if dp[i][j]:
			for k in range(n):
				if j >> k & 1 == 0 and a[i][k] == 1:
					dp[i + 1][j | 1 << k] += dp[i][j]
					dp[i + 1][j | 1 << k] %= mod
print(dp[-1][-1])


def f(s, i):
	if i == n:
		return 1
	if memo[s] != -1:
		return memo[s]
	re = 0
	for j in range(n):
		if aij[i][j] and s & 1 << j:
			re += f(s - (1 << j), i + 1)
	re = memo[s] = re % md
	return re
md = 10 ** 9 + 7
n = int(input())
aij = [list(map(int, input().split())) for _ in range(n)]
memo = [-1] * (1 << n)
s = (1 << n) - 1
print(f(s, 0))


DIV = 10 ** 9 + 7
N = int(input())
a = []
for i in range(N):
	a.append(list(map(lambda x: int(x), input().split())))
dp = [[0] * 2 ** N for i in range(N)]
for k in range(N):
	if a[0][k] == 1:
		dp[0][1 << k] = 1
for i in range(1, N):
	for b in range(2 ** N):
		if dp[i - 1][b] == 0:
			continue
		for k in range(N):
			if a[i][k] == 1 and b & 1 << k == 0:
				target = b | 1 << k
				dp[i][target] += dp[i - 1][b]
				if dp[i][target] > DIV:
					dp[i][target] %= DIV
s = 0
for i in range(2 ** N):
	s += dp[N - 1][i]
	if s > DIV:
		s %= DIV
print(s)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = [0] * (1 << n)
ans[0] = 1
mod = 10 ** 9 + 7

def popcnt(x):
	ret = 0
	for i in range(n):
		if x & 1 << i:
			ret += 1
	return ret
for bit in range(1 << n):
	if ans[bit]:
		i = popcnt(bit)
		v = 1
		for j in range(n):
			if not bit & v and a[i][j]:
				ans[bit | v] = (ans[bit | v] + ans[bit]) % mod
			v <<= 1
print(ans[-1])


mod = 10 ** 9 + 7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[-1] = 1
for i in range(N):
	bit = (1 << N - i) - 1
	while bit < 1 << N:
		for j in range(N):
			if a[i][j] == 1 and bit >> j & 1 == 1:
				dp[bit & ~(1 << j)] += dp[bit]
				dp[bit & ~(1 << j)] %= mod
		x = bit & -bit
		y = bit + x
		bit = (bit & ~y) // x >> 1 | y
print(dp[0])


import sys
INF = float('inf')
MOD = 1000000007

def bit_sum(n):
	wa = 0
	while n > 0:
		wa += n & 1
		n >>= 1
	return wa

def bit(n, k):
	return n >> k & 1

def solve(N: int, a: 'List[List[int]]'):
	dp = [0] * (1 << N)
	dp[0] = 1
	for S in range(1, 1 << N):
		i = bit_sum(S)
		for j in range(N):
			if bit(S, j) == 1 and a[i - 1][j] == 1:
				dp[S] = (dp[S] + dp[S ^ 1 << j]) % MOD
	print(dp[(1 << N) - 1])
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]
	solve(N, a)
main()


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127
N = INT()
a = [LIST() for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
for S in range(1, 1 << N):
	i = popcount(S)
	for j in range(N):
		if S >> j & 1 and a[i - 1][j] == 1:
			dp[S] += dp[S ^ 1 << j]
			dp[S] %= mod
print(dp[(1 << N) - 1])


n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]

def bitcount(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
MOD = 10 ** 9 + 7
size = 1 << n
dp = [0] * size
dp[0] = 1
for i in range(size - 1):
	num = bitcount(i)
	for c in range(n):
		if A[num][c] and 1 << c ^ i != i:
			dp[1 << c ^ i] += dp[i]
			if dp[1 << c ^ i] > MOD:
				dp[1 << c ^ i] -= MOD
print(dp[-1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
bit_count = [0]
for _ in range(N):
	bit_count += [x + 1 for x in bit_count]
dp = [0] * (1 << N)
dp[0] = 1
for i in range((1 << N) - 1):
	k = bit_count[i]
	for c in range(N):
		if A[k][c]:
			dp[1 << c ^ i] += dp[i]
answer = dp[-1] % MOD
print(answer)


N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
	i = bin(b).count('1')
	for x in range(N):
		if b >> x & 1 and A[i - 1][x]:
			dp[b] += dp[b ^ 1 << x]
	dp[b] %= MOD
print(dp[-1])


import sys
input = sys.stdin.readline

def itercomb(n, k):
	_a = (1 << k) - 1
	yield _a
	while 1:
		_x = _a & -_a
		_y = _a + _x
		_a = (_a & ~_y) // _x >> 1 | _y
		if _a >= _ALL:
			break
		yield _a
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
MOD = 10 ** 9 + 7
_ALL = 1 << n
dp = [0] * _ALL
dp[0] = 1
for m in range(1, n + 1):
	for a in itercomb(n, m):
		for (c, i) in enumerate(A[m - 1]):
			if 1 << c & a and i:
				dp[a] += dp[a ^ 1 << c]
				if dp[a] > MOD:
					dp[a] -= MOD
print(dp[2 ** n - 1])


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	A = [tuple(map(int, input().split())) for _ in range(N)]
	MOD = 10 ** 9 + 7
	N2 = 1 << N
	dp = [1] + [0 for _ in range(N2 - 1)]
	for i in range(N):
		nextdp = [0 for _ in range(N2)]
		for j in range(N2):
			if dp[j] != 0:
				for k in range(N):
					if j >> k & 1 == 0 and A[i][k] == 1:
						idx = j | 1 << k
						nextdp[idx] += dp[j]
		dp = nextdp
	print(dp[N2 - 1] % MOD)
main()


import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def dfs(state, a):
	if a == N:
		if state == (1 << N) - 1:
			return 1
		else:
			return 0
	if dp[state] != -1:
		return dp[state]
	res = 0
	for i in range(N):
		if state >> i & 1 == 0 and A[a][i] == 1:
			res += dfs(state | 1 << i, a + 1)
			res %= mod
	dp[state] = res
	return dp[state]
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split(' '))))
dp = [-1 for i in range(1 << N)]
print(dfs(0, 0))