Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###



def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            # 更新する
            # max(0, i - a)のHPにより少ない魔力消費量で行き着ければ更新する
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()

### FIXED CODE ###



def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            # 更新する
            # max(0, i - a)のHPにより少ない魔力消費量で行き着ければ更新する
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()
### BUGGY CODE ###

N = int(input())
S = ["" for _ in range(N)]
num = 0
for i in range(N):
  X = input()
  if not X in S:
    S[i] = X
    num += 1
print(num)

### FIXED CODE ###

N = int(input())
S = ["" for _ in range(N)]
num = 1
for i in range(N):
  S[i] = input()
List = sorted(S)
for j in range(N-1):
  if List[j] != List[j+1]:
    num += 1
print(num)
### BUGGY CODE ###

while 1:
    m=0
    l=[]
    n=int(input())
    if not n: break
    for i in range(n):
        j=int(input())
        if i==0:
            m+=j
        elif s*j<0:
            l.extend([m])
            m=j
        else:
            m+=j
        s=j
    l.extend([m])
    b=len(l)
    print(max([sum(l[i:j]) for j in range(1,b+1) for i in range(j)]))


### FIXED CODE ###

while 1:
    n=int(input())
    if not n:break
    dp=[0 for _ in range(n)]
    dp[0]=int(input())
    for i in range(1,n):
        v=int(input())
        dp[i]=max(dp[i-1]+v,v)
    print(max(dp))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = str(a[0])
if n%2==0:
    for i in range(1,n):
        if i%2==1:
            ans = str(a[i])+' '+ans
        else:
            ans = ans+' '+str(a[i])
else:
    for i in range(1,n):
        if i%2==0:
            ans = str(a[i])+' '+ans
        else:
            ans = ans+' '+str(a[i])
    
print(ans)

### FIXED CODE ###

import collections

def f(myList):
    ans = ''
    if len(myList)%2==0:
        for i in range(len(myList)):
            ans += str(myList[i]) + ' '
    else:
        for i in range(len(myList)):
            ans += str(myList[-(i+1)]) + ' '
    return ans[:-1]

n = int(input())
a = list(map(int,input().split()))
b = collections.deque()
for i in range(n):
    if i%2==0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
print(f(b))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count_dict = {i:{} for i in range(2)}
#print(count_dict[0])
for i in range(2):
  for j in A[i::2]:
    if j not in count_dict[i]:
      count_dict[i][j] = 1
    else:
      count_dict[i][j] += 1

candidates = [sorted(count_dict[i].items(), key=lambda kv: kv[1]) for i in range(2)]

candidates = [i[1]+j[1] for i in candidates[0] for j in candidates[1] if i[0] != j[0]]
no_move = max(candidates) if candidates != [] else len(A) // 2
print(N-no_move)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count_dict = {i:{} for i in range(2)}
#print(count_dict[0])
for i in range(2):
  for j in A[i::2]:
    if j not in count_dict[i]:
      count_dict[i][j] = 1
    else:
      count_dict[i][j] += 1

candidates = [sorted(count_dict[i].items(), key=lambda kv: kv[1], reverse=True)[:2] for i in range(2)]
candidates = [i[1]+j[1] for i in candidates[0] for j in candidates[1] if i[0] != j[0]]
no_move = max(candidates) if candidates != [] else len(A) // 2
print(N-no_move)
### BUGGY CODE ###

n = int(input())
a_lst = [int(elem) for elem in input().split()]

def calc(num, lst):
  if num in lst:
    return lst.index(num), lst[lst.index(num)+1:]
  else:
    return len(lst), []

if not 1 in a_lst:
  print(-1)
else:
  num = 1
  res = 0
  while a_lst != []:
    tmp, a_lst = calc(num, a_lst)
    res += tmp
    num += 1
  print(res)

### FIXED CODE ###

input()
nums = list(map(int, input().split()))
 
cnt = 0
cur = 1
 
for i in nums:
    if i == cur:
        cur+=1
    else:
        cnt+=1
if cur == 1:
    print(-1)
else:
    print(cnt)
### BUGGY CODE ###

N = int(input())
print(sum(range(1, N)))


### FIXED CODE ###

N = int(input())
print((N-1) * N //2)
### BUGGY CODE ###

h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

sets = [[set() for j in range(w)] for i in range(h)]
sets[0][0].add(c[0][0])
for i in range(1, h):
    for e in sets[i - 1][0]:
        sets[i][0].add(e + c[i][0])
        sets[i][0].add(abs(e - c[i][0]))
for i in range(1, w):
    for e in sets[0][i - 1]:
        sets[0][i].add(e+c[0][i])
        sets[0][i].add(abs(e-c[0][i]))
for i in range(1, h):
    for j in range(1, w):
        for e in sets[i-1][j]:
            sets[i][j].add(e+c[i][j])
            sets[i][j].add(abs(e - c[i][j]))
        for e in sets[i][j-1]:
            sets[i][j].add(e+c[i][j])
            sets[i][j].add(abs(e-c[i][j]))

print(min(sets[h - 1][w - 1]))


### FIXED CODE ###

h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]
mask = (1 << (h+w) * 80) - 1
sets = [[0 for j in range(w)] for i in range(h)]
sets[0][0] = (1 << 80+c[0][0]) | (1 << 80-c[0][0])
for i in range(1, h):
    sets[i][0] |= (sets[i - 1][0] << 80 + c[i][0]
                   ) | (sets[i - 1][0] << 80 - c[i][0])
for i in range(1, w):
    sets[0][i] |= (sets[0][i-1] << 80 + c[0][i]
                   ) | (sets[0][i-1] << 80 - c[0][i])
for i in range(1, h):
    for j in range(1, w):
        sets[i][j] |= (sets[i - 1][j] << 80 + c[i][j]
                       ) | (sets[i - 1][j] << 80 - c[i][j])
        sets[i][j] |= (sets[i][j-1] << 80 + c[i][j]
                       ) | (sets[i][j - 1] << 80 - c[i][j])
    sets[i][j] &= mask

s = bin(sets[h - 1][w - 1] + (1 << (h + w) * 80))
min_v = 1 << 80
for i in range(len(s)):
    if s[-1-i] == '1':
        min_v = min(min_v, abs(i - (h + w) * 80 + 80))
print(min_v)
### BUGGY CODE ###

n=int(input())
import math
from functools import reduce
def gcd_list(*numbers):#引数はリスト
    return reduce(math.gcd, numbers)
ans=0  
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            l=[i,j,k]
            ans+=gcd_list(*l)
print(ans)

### FIXED CODE ###

n=int(input())
import math
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        ij=math.gcd(i,j)
        if ij==1:
            ans+=n
        else:
            for k in range(1,n+1):
                ans+=math.gcd(ij,k)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
al = [input() for _ in range(h)]

inf = 10**9
m = [[inf]*w for _ in range(h)]
q = deque([])
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            m[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    ch,cw = q.popleft()
    c = m[ch][cw]
    for hi,wi in [[ch+1,cw],[ch,cw+1],[ch-1,cw],[ch,cw-1]]:
        if h>hi>=0 and w>wi>=0 and m[hi][wi]>c+1:
            m[hi][wi] = c+1
            q.append((hi,wi))

res = max([max(m[i]) for i in range(h)])
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [list(input()) for _ in range(h)]
cnt = 0

q = []
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            q.append((hi,wi))

while len(q)>0:
    nq = []
    cnt += 1
    for hi,wi in q:
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            if h>hi+d[0]>=0 and w>wi+d[1]>=0:
                if al[hi+d[0]][wi+d[1]]==".":
                    al[hi+d[0]][wi+d[1]] = "#"
                    nq.append((hi+d[0], wi+d[1]))
    q = nq

print(cnt-1)
### BUGGY CODE ###

N = int(raw_input())
R = []
for i in range(N):
    R.append(int(raw_input()))

max = R[1] - R[0]
for i in range(N - 1):
    for j in range(i + 1):
        dif = R[i+1] - R[j]
        if dif > max:
            max = dif

print max

### FIXED CODE ###

N = int(raw_input())
min = int(raw_input())
max = int(raw_input())
dif = max - min
if max < min:
    min = max

for i in range(N - 2):
    R = int(raw_input())
    if R - min > dif:
        dif = R - min
    if R < min:
        min = R

print dif
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

mod = 10**9 + 7

ans = 0
for i in range(0, N - 1):
    for j in range(i + 1, N):
        # print(bin(A[i] ^ A[j]))
        ans += int(bin(A[i] ^ A[j]), 0)
        ans %= mod
print(ans)


### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))

MOD = 10**9 + 7

answer = 0
for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x = x * 2 % MOD
    answer += x
answer %= MOD
print(answer)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
ans=0
for i in range(n):
  l=list(map(lambda x: x+1,l))
  ans+=l.count(a[i])
  l.append(-a[i])
print(ans)

### FIXED CODE ###

import collections
n=int(input())
l=list(map(int,input().split()))
a=[0]*n
b=[0]*n
for i in range(n):
  a[i]=i+1+l[i]
  b[i]=(i+1-l[i])
A=collections.Counter(a)
aa=A.most_common()
B=collections.Counter(b)

ans=0
for i in range(len(aa)):
  ans+=B[aa[i][0]]*aa[i][1]

print(ans)
### BUGGY CODE ###

from collections import Counter
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
counts = dict(Counter(a))
count = 0
while len(counts) > k:
        mins = min(counts.values())
        count += mins
        del counts[min(counts,key=counts.get)]
        
print(count)

### FIXED CODE ###

from collections import Counter
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
counts = dict(Counter(a))
counts = list(counts.values())
counts.sort()
count = 0

dev = len(counts)-k
for i in range(dev):
    count += counts[i]
        
print(count)
### BUGGY CODE ###

# ABC129D - Lamp
import sys
input = sys.stdin.readline

def main():
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] == 0
                U[i][j] == 0
            else:
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            if S[i][j] == "#":
                R[i][j] == 0
                D[i][j] == 0
            else:
                if j == W - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

                if i == H - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC129D - Lamp
import sys
input = sys.stdin.readline

def main():
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] == 0
                U[i][j] == 0
            else:
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            if S[i][j] == "#":
                R[i][j] == 0
                D[i][j] == 0
            else:
                if j == W - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

                if i == H - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    for i in range(1, n):
        for j in range(i):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = i-j if i-j < dp[i][j] else dp[i][j]
    print(max(max(dp, key=lambda x: max(x))))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
ans=set()
for i in range(1,n+1):
  for j in range(n-i+1):ans.add(s[j:j+i])
ans=sorted(list(set(ans)))
print(ans[k-1])

### FIXED CODE ###

s=input()
k=int(input())
a={s}
for i in range(k):
  for j in range(len(s)-i):a.add(s[j:j+i+1])
print(sorted(list(a))[k-1])
### BUGGY CODE ###

from itertools import permutations
n,k=map(int,input().split())
L,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    L.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
for p in permutations(X,2):
    for q in permutations(Y,2):
        u,d,l,r=max(p),min(p),min(q),max(q)
        cnt=0
        for i in L:
            if d<=i[0]<=u and l<=i[1]<=r:
                cnt+=1
        if cnt>=k:
            ans=min(ans,(u-d)*(r-l))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    if D<=i[0]<=U and L<=i[1]<=R:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(U-D)*(R-L))
print(ans)
### BUGGY CODE ###

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

friend = [[0] * n for i in range(n)]
block = [[0] * n for i in range(n)]

not_see = [set() for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    friend[a][b] = 1
    friend[b][a] = 1
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)

### FIXED CODE ###

from collections import defaultdict


# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

not_see = defaultdict(set)

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)
### BUGGY CODE ###

# https://abc084.contest.atcoder.jp/tasks/abc084_d


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    p_l = primes(10**5)
    total = [0 for _ in range(10 ** 5 + 1)]
    for i in range(3, 10 ** 5 + 1, 2):
        if i in p_l and (i + 1) // 2 in p_l:
            total[i] = 1
    for i in range(3, 10 ** 5 + 1):
        total[i] += total[i - 1]

    # print(total[:10])
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    for lr in lrs:
        print(total[lr[1]] - total[lr[0]-1])


main()






### FIXED CODE ###

# https://abc084.contest.atcoder.jp/tasks/abc084_d


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime


def main():
    p_l = primes(10**5)
    total = [0 for _ in range(10 ** 5 + 1)]
    for i in range(3, 10 ** 5 + 1):
        if p_l[i] and p_l[(i + 1) // 2]:
            total[i] = 1 + total[i - 1]
        else:
            total[i] = total[i - 1]

    # print(total[:10])
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    for lr in lrs:
        print(total[lr[1]] - total[lr[0]-1])


main()
### BUGGY CODE ###

N=int(input())
P=1
for i in range (N):
	P*=i+1
print(P%(10**9+7 ))

### FIXED CODE ###

N=int(input())
P=1
for i in range (N):
	P*=i+1
	P=P%(10**9+7)
print(P)
### BUGGY CODE ###

import sys
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
ans = 0
for i in range(n-1):
  for j in range(a[i]+i,n):
    if a[i]+a[j] == j-i:
      ans += 1
      
print(ans)

### FIXED CODE ###

import sys
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
x = [0]*n
ans = 0
for i in range(n): 
  if a[i]+i < n:
    x[a[i]+i] += 1
  if i-a[i] >= 0:
    ans += x[i-a[i]]
      
print(ans)
### BUGGY CODE ###

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

N = int(input())
a = list(map(int, input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

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

max_one = one + two + three
max_two = two + three
max_three = three

for k in range(max_three + 1):
    for j in range(max_two + 1 - k):
        for i in range(max_one + 1 - j - k):
            if i + j + k == 0:
                continue
            else:
                r = N

            if i > 0:
                r += dp[i - 1][j][k] * i
            if j > 0:
                r += dp[i + 1][j - 1][k] * j
            if k > 0:
                r += dp[i][j + 1][k - 1] * k

            dp[i][j][k] = r / (i + j + k)

print(dp[one][two][three])


### FIXED CODE ###

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

N = int(input())
a = list(map(int, input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

dp = [[[-1] * 301 for _ in range(301)] for _ in range(301)]

def dfs(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]

    if i == 0 and j == 0 and k == 0:
        return 0.0

    res = 0.0

    if i > 0:
        res += dfs(i - 1, j, k) * i
    if j > 0:
        res += dfs(i + 1, j - 1, k) * j
    if k > 0:
        res += dfs(i, j + 1, k - 1) * k
        
    res += N

    res /= i + j + k

    dp[i][j][k] = res
    return res

res = dfs(one, two, three)

print(res)
### BUGGY CODE ###

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)]
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[-1])

### FIXED CODE ###

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