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

(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1

for i in cant:
    if p[i - 1] == i:
        res = res + 1
print(res)


### FIXED CODE ###

def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


def sameroot(x, y):
    return root(x) == root(y)


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)
### BUGGY CODE ###

n,k = map(int, input().split())
INF = 10**18
dp = [INF] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
list1 = list(map(int,input().split()))
dp = [10**9]*n
dp[0] = 0

for i in range(1,n):
    for j in range(1,k+1):
        if i - j < 0:
            break
        dp[i] = min(dp[i],dp[i-j]+abs(list1[i]-list1[i-j]))

print(dp[-1])
### BUGGY CODE ###

import numpy as np

N, M = map(int,input().split())

As = sorted(list(map(int,input().split())))
BCs = []

for i in range(M):
	inputs = list(map(int,input().split()))
	BCs.append(inputs)
BCs = sorted(BCs, reverse = True, key=lambda x: x[1])

index = 0
for bc in BCs:
	b = bc[0]
	c = bc[1]

	for n in range(b):
		try:
			if As[index] < c:
				As[index] = c
				index += 1
		except:
			break
print(sum(As))


### FIXED CODE ###

import numpy as np

N, M = map(int,input().split())

As = sorted(list(map(int,input().split())))
BCs = []

for i in range(M):
	inputs = list(map(int,input().split()))
	BCs.append(inputs)
BCs = sorted(BCs, reverse = True, key=lambda x: x[1])

index = 0
for bc in BCs:
	b = bc[0]
	c = bc[1]

	for n in range(b):
		try:
			if As[index] < c:
				As[index] = c
				index += 1
			else:
				break
		except:
			break
print(sum(As))
### BUGGY CODE ###

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

maxi=-1
sum=0

for i in range(0,N-K+1):
  sum=0
  for j in range(i,i+K):
    sum += (p[j]+1)/2
  maxi=max(maxi,sum)
  
print(maxi)

### FIXED CODE ###

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

sum=[0]*N
sum_f=0

for j in range(K):
  sum_f += (p[j]+1)/2
sum[0]=sum_f
  
for i in range(1,N-K+1):
  sum[i]=sum[i-1] - (p[i-1]+1)/2 + (p[i+K-1]+1)/2
  
print(max(sum))
### BUGGY CODE ###

import numpy as np
import math

H, N = map(int, input().split())
mahou = np.array([list(map(int, input().split())) for _ in range(N)])

dmg = mahou[:, 0]
mp = mahou[:, 1]

dp = np.full(H+1, float("inf"))
dp[0] = 0

for h in range(H):
  for d, m in zip(dmg, mp):
    new_hp = min(h + d, H)
    dp[new_hp] = min(dp[new_hp], dp[h] + m)
print(int(dp[-1]))


### FIXED CODE ###

#import numpy as np
import math

H, N = map(int, input().split())
#mahou = np.array([list(map(int, input().split())) for _ in range(N)])
mahou = [list(map(int, input().split())) for _ in range(N)]


dp = [float("inf")]*(H+1)
dp[0] = 0

for h in range(H):
  for d, m in mahou:
    new_hp = min(h + d, H)
    dp[new_hp] = min(dp[new_hp], dp[h] + m)
print(int(dp[-1]))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
ans=[]
for i in range(1,N+1):
    ans.append(str(L.index(i)+1))
print(" ".join(ans))

### FIXED CODE ###

import sys
input=sys.stdin.readline
N = int(input())
L = list(map(int,input().split()))

answer = [None] * N
for i, num in  enumerate(L):
    answer[num-1] = i+1
print(*answer)
### BUGGY CODE ###

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

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

#dict = {a[i][j]: (i, j) for i in range(h) for j in range(w)}

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    
    ans = 0
    while l != r:
        y, x = dic[l - 1]
        ny, nx = dic[l + d - 1]
        
        ans += abs(ny - y) + abs(nx - x)
        l += d
        
    print(ans)

### FIXED CODE ###

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

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

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

s = [0] * (h * w)
        
for i in range(d, h * w):
    j = i - d
        
    y, x = dic[j]
    ny, nx = dic[i]
    s[i] = s[i - d] + abs(ny - y) + abs(nx - x)

q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(s[r] - s[l])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def func(D, C):
    A, B = D, D
    rests = []
    num = 0
    while True:
        if C%2:
            rests.append(A)
            C -= 1
        if C == 0:
            break
        num += C//2
        X = A+B
        if X >= 10:
            A, B = X//10, X%10
        else:
            A, B = X, X
            C //= 2

    rests = rests[::-1]
    ret, E = func_naive(rests)
    return num+ret, E

def func_naive(Xs):
    num = 0
    while True:
        if len(Xs) == 1:
            break
        B = Xs.pop()
        A = Xs.pop()
        X = A+B
        if X >= 10:
            Xs.append(X//10)
            Xs.append(X%10)
        else:
            Xs.append(X)
        num += 1
    return num, Xs[0]

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

ans = 0
Es = []
for d, c in dcs:
    num, E = func(d, c)
    ans += num
    Es.append(E)

num, E = func_naive(Es)
ans += num

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def func(D, C):
    A, B = D, D
    rests = []
    num = 0
    while True:
        if C%2:
            rests.append(A)
            C -= 1
        if C == 0:
            break
        num += C//2
        X = A+B
        if X >= 10:
            A, B = X//10, X%10
        else:
            A, B = X, X
            C //= 2

    rests = rests[::-1]
    ret, E = func_naive(rests)
    return num+ret, E

def func_naive(Xs):
    num = 0
    while True:
        if len(Xs) == 1:
            break
        B = Xs.pop()
        A = Xs.pop()
        X = A+B
        if X >= 10:
            Xs.append(X//10)
            Xs.append(X%10)
        else:
            Xs.append(X)
        num += 1
    return num, Xs[0]

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

ans = 0
Es = []
for d, c in dcs:
    num, E = func(d, c)
    ans += num
    Es.append(E)

num, E = func_naive(Es)
ans += num

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

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          t = dist[v] + 1
          dist[nv] = t
          if t > d:
            cnt += 1
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)
### BUGGY CODE ###

N,*S=open(0).read().split()
import collections

C=collections.Counter(S)
keys = [k for k, v in C.items() if v == max(C.values())]
keys.sort()

for i in keys:
    print(i)

### FIXED CODE ###

N,*S=open(0).read().split()
import collections

C=collections.Counter(S)
M=max(C.values())
keys = [k for k, v in C.items() if v == M]
keys.sort()

for i in keys:
    print(i)
### BUGGY CODE ###

n=int(input())
L_lst=sorted(list(map(int,input().split())))
i=n-2
j=n-1
cnt=0
while j>1:
    for x in range(i-1,-1,-1):
        if x==0:#0だとout of range
            if L_lst[x]+L_lst[i]>L_lst[j]:
                cnt+=1
        else:
            if L_lst[x]!=L_lst[x-1]:
                if L_lst[x]+L_lst[i]>L_lst[j]:
                    cnt+=1
                else:
                    break
    i-=1
    if i==0 or (L_lst[j])//2 >= L_lst[i]:
        j-=1
        i=j-1
print(cnt)


### FIXED CODE ###

n=int(input())
L_lst=sorted(list(map(int,input().split())))
cnt=0
for j in range(n-1,1,-1):
    i=j-1
    x=0
    while x<i:
        if L_lst[i]+L_lst[x]>L_lst[j]:
            cnt+=i-x
            i-=1
        else:
            x+=1
print(cnt)
### BUGGY CODE ###

n,x,y = map(int,input().split())

x = x-1
y = y-1

count_dict = {i : 0 for i in range(0, n)}

for i in range(n):
    for k in range(n):
        key = min(abs(i-k), abs(i-x)+abs(k-y) + 1, abs(i-y) +abs(k-x) + 1)
        count_dict[key] += 1

for i in range(1, n):
    print(count_dict[i] //2)

### FIXED CODE ###

n,x,y = map(int,input().split())

x = x-1
y = y-1

count_dict = {i : 0 for i in range(0, n)}

for i in range(n):
    for k in range(n):
        key = min(abs(i-k), abs(i-x)+abs(k-y) + 1, abs(i-y) +abs(k-x) + 1)
        count_dict[key] += 1

for i in range(1, n):
    print(count_dict[i] //2)
### BUGGY CODE ###

import sys
n = int(input())
a =[ [int(c) for c in l.split()] for l in sys.stdin]
a =a[0]
m = 1

for i in range(n):
 m=m*a[i]

if m>10**18:
 print(-1)
else:
 print(m)

### FIXED CODE ###

import sys
n = int(input())
a =[ [int(c) for c in l.split()] for l in sys.stdin]
a =a[0]
m = 1

if (0 in a)==True:
 m=0
else:
 for i in range(n):
  m*=a[i]
  if m>10**18:
   m=-1
   break

print(m)
### BUGGY CODE ###

s=input()
temp=0
tem=0
tot=0
for i in range(len(s)):
    tem=1
    temp=1
    flag=0
    for j in range(i+1,len(s)):
        if s[j]==s[i]:
            temp+=1
        tem+=1
        if temp>(tem//2 ):
            print(i+1,j+1)
            
            flag=1
            tot=1
            break
    if flag:
        break
if tot==0:
    print("-1 -1")

### FIXED CODE ###

s=input()
temp=0
tem=0
tot=0
flag=0
if s[-2]==s[-1]:
    print(len(s)-1,len(s))
else:
        
    if 1:
        for i in range(len(s)-2):
            if s[i]==s[i+1]:
                print(i+1,i+2)
                flag=1
                break
            elif s[i]==s[i+2]:
                print(i+1,i+3)
                flag=1
                break
        if flag==0:
            print("-1 -1")
### BUGGY CODE ###

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

for i in range(M):
    amax = A.index(max(A))
    A[amax] = A[amax] // 2

print(sum(A))


### FIXED CODE ###

import heapq as hq

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

#ヒープキューのために符号逆転
A=list(map(lambda x: x * (-1), A))
hq.heapify(A)

for i in range(M):
    a = hq.heappop(A) * (-1)
    hq.heappush(A, a // 2 * (-1))

print(sum(A) * (-1))
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")
### BUGGY CODE ###

def resolve():
    n,m=map(int,input().split())
    drink=[]
    ans=0
    count=0
    for i in range(n):
        tmp=list(map(int,input().split()))
        drink.append(tmp)
    drink.sort()
    while(True):
        tmp=drink.pop(0)
        if m>tmp[1]:
            ans+=tmp[0]*tmp[1]
            m-=tmp[1]
        else:
            ans+=tmp[0]*m
            break
    print(ans)


resolve()

### FIXED CODE ###

import heapq
def resolve():
    n,m=map(int,input().split())
    drink=[]
    ans=0
    count=0
    for i in range(n):
        tmp=list(map(int,input().split()))
        drink.append(tmp)
    heapq.heapify(drink)
    while(True):
        tmp=heapq.heappop(drink)
        if m>tmp[1]:
            ans+=tmp[0]*tmp[1]
            m-=tmp[1]
        else:
            ans+=tmp[0]*m
            break
    print(ans)


resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * (n + k + 10)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            if dp[i + j] == float('inf'):
                dp[i + j] = dp[i] + abs(h[i + j] - h[i])
            else:
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
        else:
            break


print(dp[n-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * (n + k + 10)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            if dp[i + j] == float('inf'):
                dp[i + j] = dp[i] + abs(h[i + j] - h[i])
            else:
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
        else:
            break


print(dp[n-1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
p=1
for i in a[:k]:
    p*=i
for i in range(k,len(a)):
    q=p//a[i-k]*a[i]
    if q>p: print("Yes")
    else: print("No")
    p=q


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k,len(a)):
    if a[i]>a[i-k]: print("Yes")
    else: print("No")
### BUGGY CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().rsplit()]
A.sort()
kekka = []
#print(A)

for i in range(len(A)):
    #A[i] = 100
    kekka.append(len([x for x in A[0:i+2] if A[i] % x == 0]))
    #print(kekka)
    answer = kekka.count(1)
print(answer)

### FIXED CODE ###

#import time

def main():
    N = int(input())
    As = list(map(int, input().split()))

    As.sort()
    amax = max(As) + 1
    lis = [True] * amax
    ans = 0

    for i in range(N-1):
        if lis[As[i]]:
            for j in range(As[i], amax, As[i]):
                lis[j] = False
            if As[i] < As[i+1]:
                ans += 1
    if lis[-1]:
        ans += 1

    return ans

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")
### BUGGY CODE ###

# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if is_stable(a, b):
    print("Stable")
else:
    print("Not stable")
for i in b:
    print(*i)


### FIXED CODE ###

# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

def bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if n > 10000:
    print("Not stable")
else:
    c = bubble_sort(a[:], n)
    if b == c:
        print("Stable")
    else:
        print("Not stable")
for i in b:
    print(*i)
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
A = [[j for j in range(n) if A[i][j]] for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in A[l-1]:
        if ((1 << i) & s):
            DP[s] += DP[~(1 << i) & s]
            DP[s] %= p
print(DP[(1 << n)-1])


### FIXED CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()
### BUGGY CODE ###

## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1] = T[v1] + [[v1,v2,d]] if(T[v1]) else [[v1,v2,d]]
    T[v2] = T[v2] + [[v2,v1,d]] if(T[v2]) else [[v2,v1,d]]

q,k = map(int, input().split())

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

### FIXED CODE ###

## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

depth = [0]*(n+1)

q,k = map(int, input().split())

is_visit = [False]*(n+1)
p,c,d = 0,k,0
depth[c] = d
is_visit[c] = True
stack = T[c]
while stack:
    p,c,d = stack.pop()
    if is_visit[c]: continue
    is_visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not is_visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])