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):
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 - bin(i).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])


if __name__ == '__main__':
    main()

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


if __name__ == '__main__':
    main()

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

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

Solution (Python):

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


if __name__ == "__main__":
    resolve()

Solution (Python):

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


if __name__ == "__main__":
    resolve()

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

Solution (Python):




import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data):
    FULLBIT = (1 << N) - 1
    memo = [-1] * (1 << N)

    def f(cursor, available):
        if cursor == N:
            return 1
        ret = memo[available]
        if ret != -1:
            return ret
        ret = 0
        j = 0
        m = available
        while m:
            if m & 1:
                
                if data[cursor * N + j]:
                    
                    ret += f(cursor + 1, available ^ (1 << j))
            j += 1
            m //= 2
        ret %= MOD
        memo[available] = ret
        return ret

    return f(0, FULLBIT)


def main():
    
    N = int(input())
    data = list(map(int, read().split()))
    print(solve(N, data))



T1 = """
3
0 1 1
1 0 1
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    """


T2 = """
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1
    """


T4 = """
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
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    102515160
    """



def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
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は64bit整数)'''

    
    x = x - ((x >> 1) & 0x5555555555555555)

    
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

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

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 popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
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))

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

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

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

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

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

Solution (Python):
def solve():
    MOD = 10**9 + 7

    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [0] * (1<<N)
    dp[0] = 1
    for S in range((1<<N)-1):
        dp[S] %= MOD
        iM = bin(S).count('1')
        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()

Solution (Python):
def solve():
    MOD = 10**9 + 7

    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [0] * (1<<N)
    dp[0] = 1
    for S in range(1, 1<<N):
        iM = bin(S).count('1') - 1
        for iW in range(N):
            if S & (1<<iW) and Ass[iM][iW]:
                S0 = S ^ (1<<iW)
                dp[S] += dp[S0]
        dp[S] %= MOD

    print(dp[-1])


solve()

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

Solution (Python):


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():
    """
    OPT[i][j] - number of pairs for first i man, with mask j=0011..01

    OPT[i+1][j|k] += OPT[i][j] k has exactly one bit set j|k != j and i+1 is compatible with k-th woman

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


if __name__ == '__main__':
    print(solve())

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

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


def count_bit_flag(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    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])


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [-1 for i in range(1 << n)]
dp[0] = 1
mod=10**9+7
def gethelp(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 += gethelp(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
print(gethelp(2**n-1, 0))

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


if __name__ == '__main__':
    main()

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

if __name__=="__main__":
    main()

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

Solution (Python):
import numpy as np

N = int(input())
A = [np.array(list(map(int, input().split()))).nonzero()[0] for _ in range(N)]

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])

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

if __name__=='__main__':
    main()

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

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

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

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

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) - 1):
    i = bitcount[bit]
    for j in range(n):
        if (a[i][j] == 1) and ((bit >> j) & 1 == 0):
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

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,1 << n):
    i = bitcount[bit]
    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) - 1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

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

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

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

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 >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])

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 >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])

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
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):
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.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
saidai = pow(2, n)
dp = [0] * saidai
dp[0] = 1

bitcnt = [0] * (saidai + 1)
for s in range(saidai):
    
    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[saidai - 1])

Solution (Python):
import sys

input = sys.stdin.buffer.readline


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    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])

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

Solution (Python):
import sys
MOD = 10 ** 9 + 7
LI = lambda: [int(x) for x in sys.stdin.readline().split()]
NI = lambda: int(sys.stdin.readline())


def main():
    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])

if __name__ == '__main__':
    main()

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

if __name__ == '__main__':
    main()

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

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

    def popcount(x):
        
        x = x - ((x >> 1) & 0x5555555555555555)

        
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  
        x = x + (x >> 8)  
        x = x + (x >> 16)  
        x = x + (x >> 32)  
        return x & 0x0000007f

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

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

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

print(dp[-1]%mod)

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