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

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ma=0
for x in range(len(a)+1):
    sa=sum(a[:x])
    for y in range(len(b)+1):
        if sa+sum(b[:y])>k:break
        ma=max(ma,x+y)
        
print(ma)

### FIXED CODE ###

import itertools
import bisect

n,m,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=list(map(int,input().split()))
aa=list(itertools.accumulate(a))
bb=list(itertools.accumulate(b))
r=0
for i,ax in enumerate(aa):
    bis=bisect.bisect_right(bb,k-ax)
    if bis==0 and ax>k:continue
    r=max(r,i+bis)
print(r)
### BUGGY CODE ###

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

n = int(input(''))
stra = input('')

for k in range(0,n):
  dic = {}
  alist = stra.split(' ')
  del alist[k]
  for i in range(0,len(alist)):
    if alist[i] in dic.keys():
      dic[alist[i]]+=1
    else:
      dic[alist[i]] = 1
  cnt = 0
  for k,v in dic.items():
    cnt += (v*(v-1))/2
  print(int(cnt))

### FIXED CODE ###

n = int(input(''))
stra = input('')

alist = stra.split(' ')
dic = {}
for i in range(0,len(alist)):
  if alist[i] in dic.keys():
    dic[alist[i]]+=1
  else:
    dic[alist[i]] = 1

all_cnt = 0    
for k,v in dic.items():
  all_cnt += (v*(v-1))/2

    
for k in range(0,n):
  cnt = 0
  key = alist[k]
  minus_cnt1 = (dic[key] * (dic[key]-1))/2
  minus_cnt2 = ((dic[key]-1) * (dic[key]-2))/2
  print(int(all_cnt -  minus_cnt1 + minus_cnt2))
### BUGGY CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    # if d[a][b] > c:
    #     d[a][b], d[b][a] = t, t
    d[a][b], d[b][a] = t, t


for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = float('inf')
for i in permutations(r):
    temp = 0
    for j in range(len(i)-1):
        temp += d[i[j]-1][i[j+1]-1]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

from collections import deque
from copy import deepcopy
def bfs(pos,map):
      while pos:
        x,y,depth=pos.popleft()
        map[x][y]="#"
        if map[x-1][y]!="#":
          pos.append([x-1,y,depth+1])
        if map[x+1][y]!="#":
          pos.append([x+1,y,depth+1])
        if map[x][y+1]!="#":
          pos.append([x,y+1,depth+1])
        if map[x][y-1]!="#":
          pos.append([x,y-1,depth+1])
      return depth
H,W=map(int,input().split())
ans=0
fence=["#"]*(W+2)
field=[fence]
for _ in range(H):
  L=list(input())
  field.append(["#"]+L+["#"])
field.append(fence)
for i in range(1,H+1):
  for j in range(1,W+1):
    if field[i][j]==".": 
      pos=deque([[i,j,0]])
      depth=bfs(pos,deepcopy(field))
      if ans<depth:
        ans=depth
print(ans)

### FIXED CODE ###

from collections import deque
from copy import deepcopy
 
def bfs(pos,map):
      while pos:
        x,y,depth=pos.popleft()
        if map[x][y]=="#":
            continue
        map[x][y]="#"
        if map[x-1][y]!="#":
          pos.append([x-1,y,depth+1])
        if map[x+1][y]!="#":
          pos.append([x+1,y,depth+1])
        if map[x][y+1]!="#":
          pos.append([x,y+1,depth+1])
        if map[x][y-1]!="#":
          pos.append([x,y-1,depth+1])
      return depth
H,W=map(int,input().split())
ans=0
fence=["#"]*(W+2)
field=[fence]
for _ in range(H):
  L=list(input())
  field.append(["#"]+L+["#"])
field.append(fence)
for i in range(1,H+1):
  for j in range(1,W+1):
    if field[i][j]==".": 
      pos=deque([[i,j,0]])
      depth=bfs(pos,deepcopy(field))
      if ans<depth:
        ans=depth
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)



### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#d=np.array(d,np.int64)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)
### BUGGY CODE ###

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v):
    print(["Yes", "No"][not v])


def debug(*v):
    if not __name__ == '__main__':
        print(*v)


# エントリーポイント
def main():
    N = input(int)
    A = input([int, N])

    count = dd(int)
    for a in A:
        count[a] += 1
    debug(count)
    for a in A:
        ans = 0
        for k, v in count.items():
            temp = v if not k == a else v - 1
            ans += (temp * (temp - 1)) // 2
        print(ans)


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


### FIXED CODE ###

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v):
    print(["Yes", "No"][not v])


# エントリーポイント
def main():
    N = input(int)
    A = input([int, N])

    count = dd(int)
    for a in A:
        count[a] += 1
    sum_ = 0
    for k, v in count.items():
        sum_ += (v * (v - 1)) // 2
    for a in A:
        print(sum_ - count[a] + 1)


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()
### BUGGY CODE ###

from math import factorial
N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 1000000007
ans = 0
if N == 1:
  ans = C[0]*2 % MOD
else:
  for i in range(N):
    for j in range(i,N):
      ans = (ans + 2**(i+N)*(N-j)*C[i]*factorial(N-i-1)//(factorial(N-j-1)*factorial(j-i))) % MOD

print(ans)

### FIXED CODE ###

n = int(input())
c = list(map(int, input().split()))
c.sort()
MOD = 1000000007
ans = 0
P = pow(4, n-1, MOD)
if n == 1:
  ans = c[0]*2 % MOD
else:
  for i in range(n):
    ans += P*c[i]*(n+1-i)
    ans %= MOD
 
print(ans)
### BUGGY CODE ###

s = input()
ans = 0
memo = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if int(s[i:j]) in memo:
            ans += 1
        x = int(s[i:j])%2019
        if x==0:
            ans += 1
            memo.append(x)
print(ans)

### FIXED CODE ###

s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(k-1,n):
    ans=(ans+a[i]*(combination(i, k-1, mod=10**9+7)))
for i in range(0,n-k+1):
    ans=(ans-a[i]*(combination(n-i-1, k-1, mod=10**9+7)))
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(comb(i,k-1)))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(n):
    for j in tree[i]:
        if i != j:
            tree[i] += tree[j]
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
    for j in tree[p - 1]:
        counter[j] += x
print(*counter)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
visited = [False] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    # tree[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
queue = deque([0])
visited[0] = True
while queue:
    now = queue.pop()
    for j in tree[now]:
        if visited[j]:
            continue
        counter[j] += counter[now]
        visited[j] = True
        queue.append(j)
print(*counter)
### BUGGY CODE ###

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

ap=a[0]
for i in range(1,n):
    ap=ap*a[i]
    
if ap<=10**18:
    print(ap)
else:
    print(-1)


### FIXED CODE ###

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

def mp(a):
    b=[]
    if len(a)==1:
        b.append(a[0]) 
    elif len(a)%2==0:
        for i in range(0,len(a),2):
            b.append(a[i]*a[i+1]) 
    else:
        for i in range(0,len(a)-1,2):
#            print(i)
            b.append(a[i]*a[i+1]) 
#        print("1",a[len(a)//2+1])
        b.append(a[len(a)-1]) 
    return b

c=aa.copy()
while len(c)>1:
    c=mp(c)   
#    print(c)
    
if c[0]<=10**18:
    print(c[0])
else:
    print(-1)
### BUGGY CODE ###

from collections import defaultdict, deque
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.P = [1]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.P[x] = 0
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.P[y] = 0
    else:
      self.par[y] = x
      self.P[y] = 0
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M = map(int, input().split())
dic = defaultdict(list)
union = UnionFind(N)

for i in range(M):
  l, r, d = map(int, input().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  union.unit(l-1, r-1)

pair = []
for x in range(N):
  if union.P[x]==1:
    pair += [x]

dist = [-1]*N
for c in pair:
  stuck = deque([(c,0)])
  dist[c] = 0
  while stuck:
    e, a = stuck.popleft()
    flag = False
    for c in dic[e]:
      p, d = c
      x = d + dist[e]
      if dist[p]==-1:
        dist[p] = x
        stuck += [(p, x)]
      elif dist[p]!=x:
        print('No')
        flag = True
        break
    if flag:
      break
  if flag:
    break
else:
  print('Yes')

### FIXED CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
used = [True]*N
dic = defaultdict(list)
for i in range(M):
  l, r, d = map(int,input().split())
  l -= 1
  r -= 1
  used[r] = False
  dic[l] += [(r,d)]

dist = [-1]*N
q = deque([])
for i in range(N):
  if used[i]:
    q += [i]
    dist[i] = 0

ans = True
while q:
  e = q.popleft()
  flag = False
  for p, d in dic[e]:
    if dist[p]==-1:
      dist[p] = d+dist[e]
      q += [p]
    elif dist[p]!=dist[e]+d:
      ans = False
      flag = True
      break
  if flag:
    break
if ans:
  if -1 not in dist:
    print('Yes')
  else:
    print('No')
else:
  print('No')
### BUGGY CODE ###

N,K,Q = map(int, input().split())

A = [int(input()) for _ in range(Q)]

P = [K for _ in range(N)]

for i in range(Q):
    ans = A[i]
    P = list(map(lambda x:x-1,P))
    P[ans-1] += 1

for i in range(N):
    if P[i] > 0:
        print('Yes')

    else:
        print('No')

### FIXED CODE ###

N,K,Q = map(int, input().split())
P = [0 for _ in range(N)]
for q in range(Q):
    num = int(input())
    P[num - 1] += 1

val = K - Q
if val > 0:
    for i in range(N):
        print('Yes')
else:
    standard = abs(val) + 1
    for i in range(N):
        if P[i] >= standard:
            print('Yes')

        else:
            print('No')
### BUGGY CODE ###

n = int(input())
A=list(map(int, input().split()))
B=[A[i]+i+1 for i in range(n)]
C=[j+1-A[j] for j in range(n)]
C2=set(C)

t=0
for i in range(n):
  if B[i] in C2:
    t+= C.count(B[i])
print(t)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
L = [i+x for i, x in enumerate(A)]
R = [i-x for i, x in enumerate(A) if i-x > 0]

from collections import Counter
P = Counter(L)
Q = Counter(R)
 
ans = 0
for k, v in P.items():
  if k in Q:
    ans += v*Q[k]
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(max(a)+1):
    ans = max(ans, a.count(i)+a.count(i-1)+a.count(i+1))
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
ans = 0
for i in range(max(a)+1):
    ans = max(ans, c[i]+c[i-1]+c[i+1])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0
    base = 1
    for i in range(60):
        counter = [0, 0]
        buf = 0
        for j in range(N):
            if A[j] & (1 << i):
                buf += counter[0]
                counter[1] += 1
            else:
                buf += counter[1]
                counter[0] += 1
        ans += buf * base
        ans %= MOD
        base = (base * 2) % MOD
    print(ans)
    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0
    base = 1
    for i in range(60):
        counter = [0, 0]
        buf = 0
        for j in range(N):
            if A[j] & (1 << i):
                buf += counter[0]
                counter[1] += 1
            else:
                buf += counter[1]
                counter[0] += 1
        ans += buf * base
        ans %= MOD
        base = (base * 2) % MOD
    print(ans)
    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
while s:
    v=s.pop()
    f[v]=0
    o+=v,
    l=[]
    for w in e[v]:
        if f[w]:
            l+=w,
            s+=w,
    e[v]=l
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
    s=1
    c1,c2=[1],[1]
    for w in e[v]:
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in e[v][::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
# print(dp1)
sz2[0]=1
dp2[0]=1
for v in o:
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
# print(dp2)
a=[]
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    sz1-=1
    sz2-=1
    a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
print('\n'.join(a))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**6
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
for i in range(n):
    u1=sz1[i]-1
    u2=sz2[i]-1
    print(dp1[i]*dp2[i]*inv[u1]*inv[u2]*fac[u1+u2]%M)
### BUGGY CODE ###

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

mod = 1000000007

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a:
        dp[i] = 0

print(dp[n])

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0

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

n = int(input())
s = input()

keys = []

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            keys.append(s[i]+s[j]+s[k])

print(len(set(keys)))


### FIXED CODE ###

n = int(input())
s = input()

keys = []

for i in range(10):
    i_str = str(i)
    if i_str not in s:
        continue
    else:
        t = s[s.index(i_str)+1:]
        for j in range(10):
            j_str = str(j)
            if j_str not in t:
                continue
            else:
                u = t[t.index(j_str)+1:]
                for k in range(10):
                    k_str = str(k)
                    if k_str in u:
                        keys.append(i_str + j_str + k_str)

print(len(keys))
### BUGGY CODE ###

import collections
K = int(input())
S = input()
N = len(S)
mod = 10**9 + 7


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


n = N + K
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, n + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

d = [0]*(K+1)
d[0] = 1
d2 = [0]*(K+1)
d2[0] = 1

for i in range(K):
    d[i+1] = d[i]*26
    d[i+1] %= mod

    d2[i+1] = d2[i]*25
    d2[i+1] %= mod

ans = 0
for i in range(K+1):
    ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
    ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import collections
    K = int(input())
    N = len(input())
    mod = 10**9 + 7

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    n = N + K
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, n + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    d = [0]*(K+1)
    d[0] = 1
    d2 = [0]*(K+1)
    d2[0] = 1

    for i in range(K):
        d[i+1] = d[i]*26
        d[i+1] %= mod

        d2[i+1] = d2[i]*25
        d2[i+1] %= mod

    ans = 0
    for i in range(K+1):
        ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
        ans %= mod
    print(ans)


main()