Problem:
 Score : 100 points    Problem Statement 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 .        Sample Input 1 3
0 1 1
1 0 1
1 1 1      Sample Output 1 3  There are three ways to make pairs, as follows ( (i, j) denotes a pair of Man i and Woman j ):   (1, 2), (2, 1), (3, 3)  (1, 2), (2, 3), (3, 1)  (1, 3), (2, 1), (3, 2)        Sample Input 2 4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0      Sample Output 2 1  There is one way to make pairs, as follows:   (1, 2), (2, 4), (3, 1), (4, 3)        Sample Input 3 1
0      Sample Output 3 0       Sample Input 4 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      Sample Output 4 102515160  Be sure to print the number modulo 10^9 + 7 .

Solution (Python):


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
    
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
    for j in range(n):
        if (i >> j) & 1:
            dp[i] += dp[i ^ (1 << j)] * a[j][cnt-1]
            dp[i]%=mod

print(dp[-1])

Solution (Python):
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))

Solution (Python):
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(~(1 << i) & s, l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1 << n)-1, n))

Solution (Python):
def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    A = [[j for j in range(n) if A[i][j]] 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 A[l-1]:
            if (1 << i) & s:
                DP[s] = (DP[s]+DP[~(1 << i) & s]) % p
    print(DP[(1 << n)-1])
main()

Solution (Python):
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))

Solution (Python):
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):
  
  k=bin(i).count("1")
  for j in range(n):
    if i&(1<<j) and a[k-1][j]:
      dp[i]+=dp[i^(1<<j)]
  dp[i]%=mod
print(dp[(1<<n)-1])

Solution (Python):
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()

Solution (Python):



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])

Solution (Python):



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])

Solution (Python):



import sys
input = sys.stdin.readline
mod=10**9+7
def main():
    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])
main()

Solution (Python):



import sys
input = sys.stdin.readline
mod=10**9+7
def main():
    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]+dp[i^(1<<j)])%mod
    print(dp[(1<<n)-1])
main()

Solution (Python):

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(num):
        cnt=0
        for i in range(N+3):
            if num&1:
                cnt+=1
            num=num>>1
        return cnt

    
    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()

Solution (Python):

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()

Solution (Python):

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()

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):

"""
bit DP
集合Sを、(s>>i)&1==1とした時,i番目の女性はマッチング済であるとし、男をループさせる。
dp[i] = 集合iから始めた場合の数(既にi状態のマッチングが終わっている場合の数)
"""
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):
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)

if __name__ == "__main__":
    main()

Solution (Python):
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 = [[0]*((1<<N)+1) for _ in range(N+1)]
    dp[0][0] = 1

    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]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

    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]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
a = [[int(_) for _ in input().split()] for _ in range(N)]
MOD = 10**9+7

dp = [[0]*((1<<N)+1) for _ in range(N+1)]
dp[0][0] = 1

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]
    
print(dp[N][(1<<N)-1]%MOD)

Solution (Python):
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 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((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)

if __name__ == "__main__":
    main()

Solution (Python):
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 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((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)

if __name__ == "__main__":
    main()

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):



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))

if __name__ == '__main__':
    main()

Solution (Python):

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)

Solution (Python):
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))

Solution (Python):
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 bit in range(1, 1 << N):
    i = 0
    for j in range(N):
        if bit >> j & 1 == 1:
            i += 1
    i -= 1
    for j in range(N):
        if a[i][j] == 1 and bit >> j & 1 == 1:
            dp[bit] += dp[bit & ~(1 << j)]
            dp[bit] %= mod
print(dp[-1])

Solution (Python):
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])

Solution (Python):
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]
                if dp[new_s] >= MOD: dp[new_s] -= MOD
print(dp[-1])

Solution (Python):
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])

Solution (Python):

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 = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_o
O - Matching / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 人の男性たちと N 人の女性たちがいます。 
男性たちには 1,2,…,N と番号が振られています。 
同様に、女性たちには 1,2,…,N と番号が振られています。

各 i,j (1≤i,j≤N) について、男性 i と女性 j の相性の良し悪しが
    整数 ai,j によって与えられます。 
ai,j=1 ならば男性 i と女性 j は相性が良く、
    ai,j=0 ならば相性が悪いです。

太郎君は、相性が良い男女どうしのペアを N 組作ろうとしています。 
このとき、各男性および各女性は
    ちょうど 1 つのペアに属さなければなりません。

N 組のペアを作る方法は何通りでしょうか？ 
109+7 で割った余りを求めてください。

制約
入力はすべて整数である。
1≤N≤21
ai,j は0 または 1 である。

解法
配るDP
こういう時は事前にいくつの値が何個bit立ってるかを計算しておくのが良い

知見
    ================================================
    |bit_length = [0]                              |
    |for i in range(n):                            |
    |    bit_length += [x + 1 for x in bit_length] |
    |で2**n-1までのbitの立っている数を前計算できる     |
    ================================================
"""


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



if __name__ == '__main__':
    solve()

Solution (Python):

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 = 1e10


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



if __name__ == '__main__':
    solve()

Solution (Python):
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])

Solution (Python):

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])

Solution (Python):
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])
if __name__=='__main__':
    main()

Solution (Python):
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])

Solution (Python):
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))