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

def main():
    import numpy as np
    def bfs(S,s,g,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v==g:
                return dist[v[0]][v[1]]
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return -1

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)-1):
        for j in range(i+1,len(spot)):
            s,g = spot[i],spot[j]
            if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
                continue
            d = bfs(S,s,g,h,w)
            if m<d:
                m = d
    print(int(m))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import numpy as np
    def bfs(S,s,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return np.max(dist)

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)):
        s = spot[i]
        if S[s[0]][s[1]]=='#':
            continue
        d = bfs(S,s,h,w)
        if m<d:
            m = d
    print(int(m))


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

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*(h+9999)
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,h+9999):
  ans=min(ans,dp[i])
print(ans)

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

n = int(input())
lst = [(elem + 1) for elem in range(n)]

if len(lst) == 1:
    print(0)
else:
    print(sum(lst[:-1]))

### FIXED CODE ###

n = int(input())
if n == 1:
    print(0)
else:
    print(n * (n - 1) // 2)
### BUGGY CODE ###

n=int(input())
renga=list(map(int,input().split()))

ans=-1
for i in range(1,n+1):
    if i in renga:
        idx=renga.index(i)
        renga=renga[idx+1:]
        brick=[renga[j] for j in range(len(renga)) if renga[j]>i]
        ans=i
        renga=brick
        #print(renga)
        continue
    else:
        break

if ans!=-1:
    ans=n-ans

print(ans)

### FIXED CODE ###

n=int(input())
renga=list(map(int,input().split()))

ans=-1
inf=0
for i in range(1,n+1):
    flag=0
    for j in range(inf,n):
        if renga[j]==i:
            ans=i
            inf=j+1
            flag=1
            break
    if flag==0:
        break

if ans!=-1:
    ans=n-ans

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

MOD = 10**9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if i in A:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD
# print(dp)
print(dp[N] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
broken = [False] * (n + 1)
for i in range(m):
    a = int(input())
    broken[a] = True
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % MOD)
### BUGGY CODE ###


import copy

H,W = map(int,input().split())

A = []

for i in range(H):

    a = input()
    la = list(a)
    A.append(la)

Q = []

for i in range(H):
    for j in range(W):

        if A[i][j] == "#":
            A[i][j] = 0
            Q.append([i,j])

ans = 0

while len(Q) > 0:

    now = Q.pop(0)

    if now[0]-1 >= 0 and A[now[0]-1][now[1]] == ".":

        A[now[0]-1][now[1]] = A[now[0]][now[1]] + 1
        Q.append ([ now[0]-1 , now[1] ])

    if now[0]+1 < H and A[now[0]+1][now[1]] == ".":

        A[now[0]+1][now[1]] = A[now[0]][now[1]] + 1
        Q.append ([ now[0]+1 , now[1] ])

    if now[1]-1 >= 0 and A[now[0]][now[1]-1] == ".":

        A[now[0]][now[1]-1] = A[now[0]][now[1]] + 1
        Q.append ([ now[0] , now[1]-1 ])

    if now[1]+1 < W and A[now[0]][now[1]+1] == ".":

        A[now[0]][now[1]+1] = A[now[0]][now[1]] + 1
        Q.append ([ now[0] , now[1]+1 ])

print(A[now[0]][now[1]])

    


### FIXED CODE ###


"""
メモ型再起？
ダイクストラじゃあきつそう
1sec!?

各点高々1回しか選ばれない工夫が必要
qにいれて少しづつ進めてく？
→各点高々4回しか選択されない
"""


H,W = map(int,input().split())

A = []
q = []

for i in range(H):

    a = list(input())
    A.append(a)

    for j in range(W):
        if a[j] == "#":
            q.append([i,j])

ans = 0
while len(q) > 0:

    #print (q)
    
    nq = []
    flag = False

    for i,j in q:
        if i > 0 and A[i-1][j] == ".":
            A[i-1][j] = "#"
            nq.append([i-1,j])
            flag = True
        if i < H-1 and A[i+1][j] == ".":
            A[i+1][j] = "#"
            nq.append([i+1,j])
            flag = True
        if j > 0 and A[i][j-1] == ".":
            A[i][j-1] = "#"
            nq.append([i,j-1])
            flag = True
        if j < W-1 and A[i][j+1] == ".":
            A[i][j+1] = "#"
            nq.append([i,j+1])
            flag = True
    q = nq
    if flag:
        ans += 1


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

n = int(input())
lis = list(map(int, input().split()))
ans = 0
for i in range(n):
    s = 0
    for j in range(i):
        if lis[i] <= lis[j]:
            s += 1
    if s == i:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
m = float('inf')
ans = 0
for i in range(n):
    m = min(m, lis[i])
    if min(m, lis[i]) == lis[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

### FIXED CODE ###

H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)
### BUGGY CODE ###

N = int(input())
Ls = list(map(int, input().split()))
Ls.sort()
# index: 0,...,N-1

ans = 0
for i in range(N-2): # i: 0,...,N-3
    for j in range(i+1, N-1): # j: i+1,...,N-2
        for k in range(j+1, N): # k: j+1,...,N-1
            if Ls[k] >= Ls[i] + Ls[j]:
                break
            if Ls[j] - Ls[i] < Ls[k]:
                ans += 1

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort() # index: 0,...,N-1

ans = 0
for i in range(N-2): # i: 0,...,N-3
    for j in range(i+1, N-1): # j: i+1,...,N-2
        # k の満たすべき条件:
        # 1. L[k] > L[j] - L[i]
        #     L[k] > L[j] なので自動的に満たす
        # 2. L[k] < L[i] + L[j]
        x = bisect.bisect_left(L, L[i]+L[j])
        # (<L[i]+L[j]), (<L[i]+L[j]), ..., (<L[i]+L[j]) | (L[i]+L[j]<=), (L[i]+L[j]<=), ...
        # | (x) より左側はOK
        # j+1 より右側はOK
        # L[j]<L[i]+L[j] と L[i]+L[j]<=L[x] より L[j]<L[x] つまり j<x
        ans += x - (j + 1)

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

# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    
    st = SegmentTree(n, f=lambda x, y: x | y, default=set([]))
    for i, ci in enumerate(c):
        st.update(i, {ci})
    
    ans = [0] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = len(st.query(l-1, r))
    
    for i in ans:
        print(i)

main()

### FIXED CODE ###

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()
### BUGGY CODE ###

N = int(input())
ans = [1] * N
for i in range(1, N):
    ans[i] = ans[i - 1] * (i + 1)

big = 10 ** 9 + 7
print(ans[N - 1] % big)


### FIXED CODE ###

N = int(input())
big = 10 ** 9 + 7
import math
print(math.factorial(N) % big)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    maxa=a[n-1]
    maxa = maxa // 2
    a[n-1] = maxa
print(sum(a))

### FIXED CODE ###

import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 0
for i in range(a, b+1):
    ans = ans ^ i
print(ans)

### FIXED CODE ###

def f(n):
    if (n+1) % 4 == 0:
        return 0
    elif (n+1) % 4 == 1:
        return n
    elif (n+1) % 4 == 2:
        return 1
    else:
        return n ^ 1
a, b = map(int, input().split())

print(f(a-1) ^ f(b))
### BUGGY CODE ###

N,K,C=map(int,input().split())
S=list(input())

#まず一つ答えをつくる これはたぶん貪欲でいける
days=[]
T=S.copy()
for i in range(N):
    if T[i]=='o':
        days.append(i)
        if C!=0:
            for j in range(1,C+1):
                if i+j>=N:
                    break
                T[i+j]='x'
    if len(days)>=K:
        break

def check(plan):
    cnt=0
    ii=0
    while ii<N:
        if plan[ii]=='o':
            cnt+=1
            ii+=C
        if cnt>=K:
            break
        ii+=1
    if cnt>=K:
        return True
    else:
        return False

p=S
for i in days:
    p[i]='x'
    if not check(p):
        print(i+1)
    p[i]='o'

### FIXED CODE ###

N,K,C=map(int,input().split())
S=input()

maekara=[]
i=1
cnt=0
while i<=N and cnt<K:
    if S[i-1]=='o':
        maekara.append(i)
        i+=C+1
        cnt+=1
    else: i+=1

usirokara=[]
j=N
cnt=0
while j>=1 and cnt<K:
    if S[j-1]=='o':
        usirokara.append(j)
        j-=C+1
        cnt+=1
    else: j-=1
usirokara=usirokara[::-1]

for i in range(K):
    if maekara[i]==usirokara[i]:
        print(maekara[i])
### BUGGY CODE ###

import math
k = int(input())

sum = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            sum += math.gcd(math.gcd(i,j), k)

print(sum)


### FIXED CODE ###

import math
N = int(input())
 
sum = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        tmp = math.gcd(i,j)
        for k in range(1, N+1):
            sum += math.gcd(tmp, k)
 
print(sum)
### BUGGY CODE ###

N = int(input())
S = input()
_d = {}
d = {}
for i in range(N-2):
    if S[i] == S[i-1] and i >= 1: continue
    for j in range(i+1, N-1):
        _st = ''.join([S[i], S[j]])
        if _st in _d: continue
        else: _d[_st] = True
        for k in range(j+1, N):
            st = ''.join([S[i], S[j], S[k]])
            d[st] = True
print(len(d))

### FIXED CODE ###

N = int(input())
S = input()
d = {}
k1 = [0 for i in range(10)]
for i in range(N-2):
    if k1[int(S[i])] != 0: continue
    k1[int(S[i])] += 1
    k2 = [0 for i in range(10)]
    for j in range(i+1, N-1):
        if k2[int(S[j])] != 0: continue
        k2[int(S[j])] += 1
        for k in range(j+1, N):
            st = ''.join([S[i], S[j], S[k]])
            d[st] = True
print(len(d))
### BUGGY CODE ###

# AGC033A
# http://drken1215.hatenablog.com/entry/2019/05/05/223200
# を参考に解いた
# 多点スタートと考えて解く

from collections import deque
# 入力
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

# 4方向を定義
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# BFSのためのデータ構造
dist = [[-1] * W for _ in range(H)]
que_x = deque()     # H
que_y = deque()     # W

# 多点スタート地点を決める
# スタート地点は0とする
for i in range(H):
    for k in range(W):
        if field[i][k] == "#":
            dist[i][k] = 0
            que_x.append(i)
            que_y.append(k)

# 多点スタート
# 0のところから順に1を増やしていく
# ex): 3地点a, b, cからスタートとすると
# aから周囲4箇所に1をつける -> bから周囲4箇所に1をつける -> cから周囲4箇所に1をつける
# aの周囲4箇所の内1点から周囲4箇所に2をつける -> aの周囲4箇所の内2点目から周囲4箇所に2をつける
# aの周囲4箇所が終われば次はbの周囲4箇所，それが終わればcの周囲4箇所
while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
            continue
        if dist[nx][ny] == -1:      # まだ見ていない時
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1       # 距離の更新

# distの最大値が答え (= 最も遠いところ)
tmp = [0] * H
for i in range(H):
    tmp[i] = max(dist[i])

print(max(tmp))

### FIXED CODE ###

# AGC033A
# http://drken1215.hatenablog.com/entry/2019/05/05/223200
# を参考に解いた
# 多点スタートと考えて解く

from collections import deque
# 入力
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

# 4方向を定義
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# BFSのためのデータ構造
dist = [[-1] * W for _ in range(H)]
que_x = deque()     # H
que_y = deque()     # W

# 多点スタート地点を決める
# スタート地点は0とする
for i in range(H):
    for k in range(W):
        if field[i][k] == "#":
            dist[i][k] = 0
            que_x.append(i)
            que_y.append(k)

# 多点スタート
# 0のところから順に1を増やしていく
# ex): 3地点a, b, cからスタートとすると
# aから周囲4箇所に1をつける -> bから周囲4箇所に1をつける -> cから周囲4箇所に1をつける
# aの周囲4箇所の内1点から周囲4箇所に2をつける -> aの周囲4箇所の内2点目から周囲4箇所に2をつける
# aの周囲4箇所が終われば次はbの周囲4箇所，それが終わればcの周囲4箇所
while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
            continue
        if dist[nx][ny] == -1:      # まだ見ていない時
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1       # 距離の更新

# distの最大値が答え (= 最も遠いところ)
tmp = [0] * H
for i in range(H):
    tmp[i] = max(dist[i])

print(max(tmp))
### BUGGY CODE ###

from itertools import combinations as com
def tri(a,b,c):
  if a+b>c and b+c>a and c+a>b:
    return 1
  else:
    return 0
n=int(input())
L=list(map(int,input().split()))
ans=0
for i,j,k in com(L,3):
    ans+=tri(i,j,k)
print(ans)
        

### FIXED CODE ###

import bisect
n=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

a,b = map(int,input().split())

counter = 0
primes = [2, 3]

for n in range(5, min(a,b), 2):
    isprime = True
    for i in range(1, len(primes)):
        counter += 1
        if primes[i] ** 2 > n:
            break
        counter += 1
        if n % primes[i] == 0:
            isprime = False
            break
    if isprime:
        primes.append(n)

ans = 1
for i in primes:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)

### FIXED CODE ###

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


a,b = map(int,input().split())

g = gcd(a,b)


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

if temp!=1:
    arr.append([temp, 1])

print(len(arr)+1)
### BUGGY CODE ###

#!/usr/bin/env python3
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

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = deque()
    q.append((0, 0))
    while q:
        p, i = q.popleft()
        ai = a[i]
        i1 = i + 1
        for j in range(n):
            if ai[j]:
                j1 = 1 << j
                if p & j1:
                    continue
                pj1 = p | j1
                dp[pj1] += dp[p]
                if i1 == n: continue
                q.append((pj1, i1))

    print(dp[-1] % mod)


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
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

#solve
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]
    # print(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


#main
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N,W = map(int, input().split())
nupList = [map(int, input().split()) for _ in range(N)]
dp = [0] * (W + 1)

for w, v in nupList:
    for j in range(W, w - 1, -1 ):
        dp[j] = max(dp[j] , dp[j - w] + v)

print(dp[W])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())