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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys
sys.setrecursionlimit(int(1e5))


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = map(lambda x: x.strip(), pair)
        l1, l2 = len(w1), len(w2)
        print(lcs_recursive(w1, w2, l1, l2))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from itertools import accumulate

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        a = list(accumulate(memo))[:-1]
        if set(a[:-1]) == n:
            break
    print(*a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


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

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, k):
    global a
    mod = int(1e9 + 7)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        csum = [0] + list(dp[i - 1])
        for j in range(k + 1):
            csum[j + 1] += csum[j]
            csum[j + 1] -= mod if csum[j + 1] >= mod else 0
        for j in range(1, k + 1):
            dp[i][j] = csum[j + 1] - csum[max(0, j - a[i])]
            dp[i][j] += mod if dp[i][j] < 0 else 0
    return(dp[n][k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
a.insert(0, 0)
print(f(n, k))


### FIXED CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))
### BUGGY CODE ###

import collections
n,m = map(int,input().split())
p = list(map(int,input().split()))
base = 0
basemap = []
for i in range(n):
	if (i+1) == p[i]:
		base += 1
		basemap.append(i+1)

branch = dict()
for i in range(1,n+1):
	branch[i] = []

for i in range(m):
	x,y = map(int,input().split())
	branch[x].append(y)
	branch[y].append(x)
compare = [0 for i in range(n+1)]
for i in range(1,n+1):
	if branch[i] != []:
		compare[i] = 1

arrival = [0 for i in range(n+1)]
ans = []
q = []

while arrival != compare:
	counter = base
	for i in range(1,n+1):
		if arrival[i] == 0 and compare[i] == 1:
			q.append(i)
			arrival[i] = 1
			break
	section = [q[0]]
	while len(q) > 0:
		next = branch[q[0]]
		for i in range(len(next)):
			if arrival[next[i]] == 0:
				section.append(next[i])
				arrival[next[i]] = 1
				q.append(next[i])
		q.pop(0)
	psec = []
	for i in range(len(section)):
		psec.append(p[section[i]-1])
	t = section + psec + basemap
	search = collections.Counter(t)
	for i in search:
		if search[i] == 2:
			 counter += 1
	ans.append(counter)
print(max(ans))

### FIXED CODE ###

import collections
n,m = map(int,input().split())
p = list(map(int,input().split()))
base = 0
basemap = []
for i in range(n):
	if (i+1) == p[i]:
		base += 1
		basemap.append(i+1)

branch = dict()
for i in range(1,n+1):
	branch[i] = []

for i in range(m):
	x,y = map(int,input().split())
	branch[x].append(y)
	branch[y].append(x)
compare = [0 for i in range(n+1)]
for i in range(1,n+1):
	if branch[i] != []:
		compare[i] = 1

arrival = [0 for i in range(n+1)]
ans = []
q = []

ind = 1
while arrival != compare:
	counter = base
	while not(arrival[ind] == 0 and compare[ind] == 1):
		ind += 1
	q.append(ind)
	arrival[ind] = 1
	section = [q[0]]
	while len(q) > 0:
		next = branch[q[0]]
		for i in range(len(next)):
			if arrival[next[i]] == 0:
				section.append(next[i])
				arrival[next[i]] = 1
				q.append(next[i])
		q.pop(0)
	psec = []
	for i in range(len(section)):
		psec.append(p[section[i]-1])
	t = section + psec + basemap
	search = collections.Counter(t)
	for i in search:
		if search[i] == 2:
			 counter += 1
	ans.append(counter)
print(max(ans))
### BUGGY CODE ###

#from collections import deque
#import copy

x,y,z,ansk=(int(i) for i in input().split())
#print(x,y,z,k)

a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

mylist=[0 for i in range(x*y)]
k=0
for i in range(x):
  for j in range(y):
    mylist[k]=a[i]+b[j]
    k+=1
mylist.sort(reverse=True)
if len(mylist)>3001:
  mylist=mylist[:3001]
#print(mylist)

k=0
mylist1=[0 for i in range(x*y*z)]
for i in range(x*y):
  for j in range(z):
    mylist1[k]=mylist[i]+c[j]
    k+=1
mylist1.sort(reverse=True)

if len(mylist1) > 3001:
  mylist1 = mylist1[:3001]
  
for i in range(ansk):
  print(mylist1[i])

### FIXED CODE ###

#import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

#k=3000
#a=[int(i) for i in range(1000)]
#b=[int(i) for i in range(1000)]
#c=[int(i) for i in range(1000)]
x=[]
for h in range(len(a)):
    for i in range(len(b)):
        if (h+1)*(i+1) <=k:
            for j in range(len(c)):
                if (h+1)*(i+1)*(j+1) <=k:
                    x.append(a[h]+b[i]+c[j])

x.sort(reverse=True)
for i in range(k):
  print(x[i])
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


for i in range(N-1):
  for j in range(1, min(K+1, N - i)):
    dp[i+j]=min(dp[i+j], dp[i]+ abs(h[i+j]-h[i]))
print(dp[N-1])


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

# dp=[0 for i in range(N)]
dp = [float("inf")]*(N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])


for i in range(N-1):
  for j in range(1, min(K+1, N - i)):
    dp[i+j]=min(dp[i+j], dp[i]+ abs(h[i+j]-h[i]))
print(dp[N-1])
### BUGGY CODE ###

N = int(input())

ans = [0] * 10000

for i in range(1, 200):
    for j in range(1, 200):
        for k in range(1, 200):
            z = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if z < 10000:
                ans[z] += 1

for x in range(1, N+1):
    print(ans[x])


### FIXED CODE ###

from numba import jit

N = int(input())

@jit
def f():
    ret = [0] * 10001

    for i in range(1, 200):
        for j in range(1, 200):
            for k in range(1, 200):
                z = i**2 + j**2 + k**2 + i*j + j*k + k*i
                if z < 10001:
                    ret[z] += 1

    return ret


ans = f()

for x in range(1, N+1):
    print(ans[x])
### BUGGY CODE ###

import math

A, B, N = tuple(map(int, input().split()))

m = 0
n = 1

def cal(x):
  return math.floor(A*x/B)-A*math.floor(x/B)

def Bceil(x):
  return B*(math.floor((x+1)/B)+1)-1

while n<N:
  c = Bceil(n)
  n = min(N, c)
  m = max(cal(n), m)
  
print(m)

### FIXED CODE ###

import math

A, B, N = tuple(map(int, input().split()))

m = 0
n = 1

def cal(x):
  return math.floor(A*x/B)-A*math.floor(x/B)

while n<N:
  c = B*(math.floor((n+1)/B)+1)-1
  n = min(N, c)
  m = max(cal(n), m)
  if (A*n)%B == 0:
    break
  
print(m)
### BUGGY CODE ###

r, g, b, n = list(map(int, input().split()))
ans = 0
for i in range(n//r+1):
  for j in range(n//b+1):
    ij = i*r + j*b
    k = (n-ij)//g
    if not (i==k==j==0) and (k>=0 and (n-ij)%g==0):
      ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = list(map(int, input().split()))
ans = 0
for i in range(n//r+1):
  for j in range(n//b+1):
    ij = i*r + j*b
    k = (n-ij)//g
    if not (i==k==j==0) and (k>=0 and (n-ij)%g==0):
      ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    answer = 10**19

    x_set = sorted(list(set(x)))
    y_set = sorted(list(set(y)))
    x_combination = list(itertools.combinations(x_set,2))
    y_combination = list(itertools.combinations(y_set,2))

    
    for x_l, x_u in x_combination:
        for y_l, y_u in y_combination:
            count = 0
            for i in range(N):
                if y_l <= y[i] <= y_u and x_l <= x[i] <= x_u:
                    count +=1
            if count >= K:
                answer = min(answer,(y_u-y_l)*(x_u-x_l))

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    answer = 10**19

    x_set = sorted(list(set(x)))
    y_set = sorted(list(set(y)))
    x_combination = list(itertools.combinations(x_set,2))
    y_combination = list(itertools.combinations(y_set,2))

    
    for x_l, x_u in x_combination:
        for y_l, y_u in y_combination:
            count = 0
            for i in range(N):
                if y_l <= y[i] <= y_u and x_l <= x[i] <= x_u:
                    count +=1
            if count >= K:
                answer = min(answer,(y_u-y_l)*(x_u-x_l))

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

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

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))

if k == 0:
	print(max(a))
	exit()

suki = max(a)
kirai = 0
a.sort(key= lambda x: -x)
while int(suki) != int(kirai):
	targ = (suki+kirai)/2
	cnt = 0
	mode = 1
	for i in range(n):
		motome = math.ceil(a[i] / targ)-1
		if motome <= 0:
			break
		cnt += motome
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))

### FIXED CODE ###

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))

if k == 0:
	print(max(a))
	exit()

suki = 1000000000
kirai = 0
while int(suki) != int(kirai):
	targ = (suki+kirai)/2
	cnt = 0
	mode = 1
	for i in range(n):
		cnt += (a[i]-1)//targ
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

num_max_r = n//r
num_max_g = n//g

ans = 0
for num_r in range(num_max_r + 1):
    for num_g in range(num_max_g + 1):
        ball_rg = num_r*r + num_g*g
        ball_b = n - ball_rg
        
        if ball_b >= 0 and ball_b % b == 0:
            ans += 1

print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

num_max_r = n//r

ans = 0
for num_r in range(num_max_r + 1):
    
    n_r = n - num_r*r
    num_max_g = n_r//g
    
    for num_g in range(num_max_g + 1):
        n_r_g = n_r - num_g*g
        
        if n_r_g >= 0 and n_r_g % b == 0:
            ans += 1

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

k = int(input())

n = 1
m = 7
while True:
  if k == 2:
    print('-1')
    exit()
  if m % k != 0:
    n += 1
    m += 7*(10**(n-1))
  else:
    print(n)
    exit()

### FIXED CODE ###

k = int(input())
m = 0

for i in range(1, k+1):
  if i == 1:
    m = 7
  else:
    m = (m*10 + 7) % k
  if m % k == 0:
    print(i)
    exit()
    
print('-1')
### BUGGY CODE ###

import itertools
d, g = map(int, input().split())

lst = [list(map(int, input().split())) for i in range(d)]
#print(lst)

new_lst = [[] for i in range(len(lst))]

for i, j in enumerate(lst):
    #print(i, j)
    for k in range(j[0] + 1):
        new_lst[i].append([k, (k * 100 * (i + 1))])
        if k == j[0]:
            new_lst[i][k][1] += j[1]
        
#print(new_lst)
min_ac = 1000

for i in itertools.product(*new_lst):
    ac = 0
    points = 0
    #print(i)
    for j in range(len(lst)):
        ac += i[j][0]
        points += i[j][1]
    if points >= g:
        if ac <= min_ac:
            min_ac = ac

print(min_ac)

### FIXED CODE ###

d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

min_ac1 = 1000
min_ac2 = 1000
for i in range(2 ** d):
    points = 0
    ac = 0
    for j in range(d):
        if ((i >> j) & 1) == 1:
            points += pc[j][0] * 100 * (j + 1) + pc[j][1]
            ac += pc[j][0]
    if points < g:
        l = "{:010b}".format(i)
        l = l[10-d:]
        for k in range(d):
            if l[k] == "0":
                tmp = k
                break
        tmp = -(tmp - d)
        if (g - points + tmp * 100 - 1) // (tmp * 100) < pc[tmp - 1][0]:
            tmp_ac = ac + (g - points + tmp * 100 - 1) // (tmp * 100)
            if tmp_ac < min_ac1:
                min_ac1 = tmp_ac
    if points >= g:
        if ac < min_ac2:
            min_ac2 = ac
    #print(bin(i), ac, points, min_ac1, min_ac2)
print(min(min_ac1, min_ac2))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
x=[y+s for y,s in zip(disten,distsneek)]
ans=[min(x[i:N+1]) for i in range(N,0,-1)]
big=10**15
for i in range(-1,-1*N-1,-1):
    print(big-ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
ans=[0]*(N+1)
ans[N]=disten[N]+distsneek[N]
for i in range(N-1,0,-1):
    ans[i]=min(ans[i+1],disten[i]+distsneek[i])
big=10**15
for i in range(1,N+1):
    print(big-ans[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 m in range(1, k + 1):
            sum += math.gcd(math.gcd(i, j), m)
print(sum)

### FIXED CODE ###

from math import gcd

k = int(input())
sum = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for m in range(1, k + 1):
            sum += gcd(gcd(i, j), m)
print(sum)
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(n):
    ans += i
    
print(ans)

### FIXED CODE ###

n = int(input())

print(n*(n-1)//2)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

b = []

for i in range(n):
    b.append(a[i])
    b = b[::-1]

print(*b)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

even = []
odd = []

for i in range(n):
    if i % 2 == 0:
        odd.append(a[i])
    else:
        even.append(a[i])

if n % 2 == 0:
    even.reverse()
    ans = even + odd
    print(*ans)
else:
    odd.reverse()
    ans = odd + even
    print(*ans)
### BUGGY CODE ###

from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで
 
def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
X = inp()
A = 0
need = 0
tmp = 0
while 1:
  B = 1
  if A**5>X:
    need = 1
  else:
    need = -1
  reverse = 0
  if check(A,B,X):
    print(str(A)  + " " + str(B))
    break
  else:
    while 1:
      if B < A and A-X <= B:
        if check(A,B,X):
          print(str(A)  + " " + str(B))
          tmp = 1
          break
      else:
        break
      if reverse == 0 and need == -1:
        B = (-1)*B
        reverse = 1
      elif reverse == 1 and need == 1:
        B = (-1)*B
        B = B + 1
        reverse = 0
      elif reverse == 0 and need == 1:
        B = B + 1
      elif reverse == 1 and need == -1:
        B = B -1
  A += 1
  if tmp:
    break
     

### FIXED CODE ###

from math import ceil #切り上げ
import numpy as np
import sys
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで
 
def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
X = inp()
for A in range(-118,120):
  for B in range(-119,119):
    if check(A,B,X):
      print(str(A) + " " + str(B))
      sys.exit()
### BUGGY CODE ###

n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

oya = [0] * (n+1)
E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [1]
t = 0

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    for i in E[x]:
        if V[i] == 0:
            oya[i] = x
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q.append(i)
            #print(Q)

while t < len(Q):
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

### FIXED CODE ###

n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [0] * (n+2)
Q[0] = 1
t = 0
r = 1

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    global r
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q[r] = i
            r += 1
            #print(Q)

while t != r:
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))
### BUGGY CODE ###

N = int(input())
a = [[int(_) for _ in input().split()] for _ in range(N)]
MOD = 10**9+7

dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for s in range(1<<N):
        if dp[i][s] == 0:
            continue
        for j in range(N):
            jb = 1<<j
            if not (s&jb) and a[i][j]:
                dp[i+1][s|jb] += dp[i][s]
    
print(dp[-1][(1<<N)-1]%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()