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

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()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    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():

    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)]
    bit_count = [0]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    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]
    print(dp[m-1]%mod)

def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    E()

Solution (Python):

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()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    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():

    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)]
    bit_count = [0]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    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


if __name__ == "__main__":
    E()

Solution (Python):

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()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    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


if __name__ == "__main__":
    E()

Solution (Python):
from numpy import*
M=10**9+7
n,*a=open(0)
n=int(n)
d=zeros(2**n,'u8')
d[0]=1
for a in a:
  b,d=d,zeros(2**n,'u8')
  for i,a in enumerate(map(int,a.split())):
    if a:
      j=2**i
      d[j:]+=b[:-j]
  d%=M
print(d[-1])

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

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

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

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

Solution (Python):


import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        def numberOfSetBits(i):
            i = i - ((i >> 1) & 0x55555555)
            i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
            return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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()

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

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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])

Solution (Python):


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

def bitcount(i): 
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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])

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

Solution (Python):
import itertools
import fileinput
 
 
def solve_match(match_matrix):
    size = len(match_matrix)

    combo_list = [0] * (2**size)

    combo_indexes = [[] for _ in range(size + 1)]
    for i in range(2**size):
        count = 0
        n = i
        while (n): 
            count += n & 1
            n >>= 1
        combo_indexes[count].append(i)

    for col in range(size):
        for combo in combo_indexes[col + 1]:
            if col == 0:
                for i in range(size):
                    if (combo & (1 << i)):
                        combo_list[combo] = match_matrix[i][col]
                        break
            else:
                s = 0
                cnt = 0
                for i in range(size):
                    flag = 1 << i
                    if (combo & flag) and match_matrix[i][col] == 1:
                        s += combo_list[combo & (~flag)]
                        cnt += 1
                        if cnt == col + 1:
                            break
                
                combo_list[combo] = s % (10**9 + 7)
    return combo_list[-1]
 
 
inp = fileinput.FileInput()
n = int(inp.readline())
 
arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])
 
print(solve_match(arr))

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

Solution (Python):
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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])

Solution (Python):


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 = (1<<m)-1
    while a < _ALL:
        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
        x = a & -a
        y = a + x
        a = (((a & ~y) // x) >> 1) | y


print(dp[2**n-1])

Solution (Python):


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

Solution (Python):


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

Solution (Python):
range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

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

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


if __name__ == "__main__":
    main()

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

Solution (Python):


import sys
input = sys.stdin.readline

bit = lambda s, j: (s >> j) & 1

def f(n, a):
    mod = int(1e9 + 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))

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

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

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

print(dfs((1<<n)-1,n-1))

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
 
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10**9 + 7


dp = [-1] * (1 << n)
dp[(1 << n) - 1] = 1

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

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

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

print(dfs(0, 0))

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

Solution (Python):


MOD = 1000000007

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


dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1, 1 << n):
    i = bin(mask).count('1') - 1  
    for j in range(n):
        if a[i][j] == 1 and mask & (1 << j):
            dp[mask] += dp[mask ^ (1 << j)]
            dp[mask] %= 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

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

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


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