Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        d = dp[i]
        if e[-1] < c:
            d = e+[c]
            ans[i] = x+1
        else:
            d = e.copy()
            ans[i] = x
        for j in range(x-1,-1,-1):
            if j == 0 and d[j] > c:
                d[j] = c
            elif d[j] > c and d[j-1] < c:
                d[j] = c
                
for i in ans[1:]:
    print(i)

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)
s = input()
pirnt(s[0:3]='7'+s[4:])

### FIXED CODE ###

s = input()
print(s[:3]+'8'+s[4:])
n = int(input())
y = []
for i in n:
    a = int(input())
    x = 1/a
    y.append(x)

s = sum(y)
an = 1/s

print(s)

### FIXED CODE ###

n = int(input())
y = []

a = input().split()
for i in range(n):
    x = 1/int(a[i])
    y.append(x)
#print(y)

s = sum(y)
an = 1/s

print(an)
A,B = map(int,input().split())
C = [1,2,3]
C.remove(A)
C.remove(B)
print(C)

### FIXED CODE ###

A = int(input())
B = int(input())
C = [1,2,3]
C.remove(A)
C.remove(B)
print(C[0])
s=input
if s == "Sunny"
print("Cloudy")
if s == "Cloudy"
print("Rainy")
if s == "Rainy"
print("Sunny")

### FIXED CODE ###

s = input()
if s == "Sunny":
    print("Cloudy")
elif s == "Cloudy":
    print("Rainy")
elif s == "Rainy":
    print("Sunny")
list = input().split()
a = int(list[0])
b = int(list[1])

if a * b % 2 == 0:
  print(Even)
else:
  print(Odd)

### FIXED CODE ###

list = input().split()
a = int(list[0])
b = int(list[1])

if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")
a,b = input().split()
if (a*b%2 = 1):
    print("0dd")
else:
    print("Even")

### FIXED CODE ###

(a,b)=map(int,input().split())
if a*b%2==0:
  print("Even")
else:
  print("Odd")
N = int(input())
ts = fetch_Hosu(N)

le = len(ts)
numl = [0]* 15

for i in range(15):
    tmp = int(ts[2*i+1:2*i+3])
    
    if tmp ==1:
        numl[i]  += 11
    elif tmp ==11:
        if i>1:
            numl[i-1]  += 11
        numl[i]  += 1
    else:
        numl[i]  += tmp
    
#     print(numl)

# print(numl)

for j in range(len(numl)):
    if numl[14-j]==21:
        numl[13-j]  += 11
        numl[14-j]  = 1

    if numl[14-j]==12:
        numl[14-j]  = 0
    
    if numl[14-j]==22:
        numl[14-j]  = 10
    
# print(numl)
outttt = ["{0:02d}".format(i) for i in numl]
# print(outttt)
ttt=""
for k in range(len(outttt)):
    ttt += outttt[k]

ttt += ts[-1]

if int(ttt)==0:
    print(0)
else:
    tetee = str(ttt)
    tpl = tetee[2:].find("1")
    print(tetee[tpl+2:])

### FIXED CODE ###

N=int(input())

lr = ""
i=1

if N==0:
    print(0)

else:    
    while N!=0:
        if N%(2**i)!=0:
            lr = "1" + lr
            N = N - (-2)**(i-1)
        else:
            lr = "0" + lr

        i+=1

    print(lr)
A,B,K=map(int,input().split())
div=[]
 for i in range(1,A):
     if(A%i==0 and B%i==0):
         div.append(i)
div.sort()
print(div[len(div)-K])


### FIXED CODE ###

A,B,K=map(int,input().split())
listAB=[]
for i in range(min(A,B)):
    if A%(i+1)==0 and B%(i+1)==0:
        listAB.append(i+1)
listAB.sort(reverse=1)
if A==1 and B==1:
    print(1)
else :
    print(listAB[K-1])
s = int(input())
#最後に切った場所がiであるようなパターンの数をdp[i]とする
dp=[0]*(s+1)
dp[0]=1
if s<3:
  print("0")
for i in range(3,s+1):
  dp[i]=dp[i-1]+dp[i-3]
  dp.append(dp[i])
  score=dp[s]%(10**9+7)
print(score)
  

### FIXED CODE ###

s = int(input())
#最後に切った場所がiであるようなパターンの数をdp[i]とする
dp=[0]*(s+1)
dp[0]=1
if s<3:
  print("0")  
else:
  for i in range(3,s+1):
    dp[i]=dp[i-1]+dp[i-3]
    dp.append(dp[i])
    score=dp[s]%(10**9+7)
  print(score)
while 1:
 m,f,r=map(int,input().split());s=m+f
 if m*f<-1:break
 if m==-1 or f==-1 or s<30:print('F')
 elif s>79:print('A')
 elif s>64:print('B')
 elif s>49 or r>49:print('C')
 else:print('D')

### FIXED CODE ###

while 1:
 m,f,r=map(int,input().split());s=m+f
 if r<0>s:break
 print('F'if(m*f<0)+(s<30)else'D'if s<50>r else'C'if s<65 else'B'if s<80 else'A')
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
ans=[]
for i in range(8):
  binstr=bin(i)[2:]
  binstr.zfill(3)
  b=[]
  for j in range(n):
    c=0
    for k in range(3):
      if binstr[k]=="1":
        c+=a[j][k]
      else:
        c+=-a[j][k]
    b.append(c)
  b.sort()
  ans.append(sum(b[:m]))
print(max(ans))

### FIXED CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
ans=[]
for i in range(8):
  binstr=format(i,"b").zfill(3)
  b=[]
  for j in range(n):
    c=0
    for k in range(3):
      if binstr[k]=="1":
        c+=a[j][k]
      else:
        c+=-a[j][k]
    b.append(c)
  b.sort(reverse=True)
  ans.append(sum(b[:m]))
print(max(ans))
nums = map(int, input().split())

sorted_nums = sorted(nums)

print(' '.join(sorted_nums))

### FIXED CODE ###

nums = map(int, input().split())

sorted_nums = sorted(nums)

print(' '.join(map(str, sorted_nums)))
# coding: utf-8
# Your code here!

n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

memo = [-1]*n

def longest(v): #nを終点とするlongest
    if memo[v] >= 0:
        return memo[v]
    else:
        c=0
        for j in oya[v]:
            c = max(c,longest(j)+1)
        memo[v] = c
        return c

for i in range(n):
    longest(i)

print(max(memo))    
#print(memo)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)

n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

memo = [-1]*n

def longest(v): #nを終点とするlongest
    if memo[v] >= 0:
        return memo[v]
    else:
        c=0
        for j in oya[v]:
            c = max(c,longest(j)+1)
        memo[v] = c
        return c

for i in range(n):
    longest(i)

print(max(memo))    
#print(memo)
n=int(input())
p=[1 for i in range(10000)]
p[0]=0
p[1]=0
for i in range(2,n+1):
  if p[i]==1:
  	for j in range(i*i,n+1,i):
      p[j]=0
ans=1
for i in range(2,n+1):
  if p[i]:
    c=0
    k=i
    while n//k>0:
      c=c+(n//k)%m
      k=k*k
    ans=(ans*((c+1)%m))%m
print(ans)
    
    
      
      


### FIXED CODE ###

from math import factorial

n = int(input())
f = factorial(n)

mod = 10 ** 9 + 7

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

ans = 1
for p in primes(n):
    temp = 1
    while f % p == 0:
        temp += 1
        f //= p
    ans = (ans * temp) % mod
print(ans)
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
K = int(input())
A = []
ans = 1


for i in range(K):
  n = int(str(N)[0])
  dig = len(str(N)) - 1
  A.append([n, dig])
  N -= n * 10**dig


for i in range(K):
  if A[i][1] >= K-i:
    ans += comb(A[i][1], K-i) * 9 ** (K-i) 
  ans += (A[i][0]-1) * comb(A[i][1], K-i-1) * 9 ** (K-i-1)
#  print(ans)

print(ans)

### FIXED CODE ###

import math
def comb(n, r):
  if n >= r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
N = int(input())
K = int(input())
A = []
ans = 0


for i in range(K):
  n = int(str(N)[0])
  dig = len(str(N)) - 1
  A.append([n, dig])
  N -= n * 10**dig
  if N == 0:
    break
#print(A)

for i in range(len(A)):
  if A[i][1] >= K-i:
    ans += comb(A[i][1], K-i) * 9 ** (K-i) 
#    print(ans)
  ans += (A[i][0]-1) * comb(A[i][1], K-i-1) * 9 ** (K-i-1)
#  print(ans)
if len(A) == K:
  ans += 1


print(ans)
d=[1]+[0]*12
for c in input():
	e=[0]*13
	for k in([c],range(10))[c>'9']:
		for j in range(13):t=(j*10+k)%13;e[t]+=d[j];e[t]%=10**9+7
	d=e
print(d[5])

### FIXED CODE ###

d=[1]+[0]*12
for i,c in enumerate(input()):
 p=[0]*13
 for j in range(13):
  for k in range(10):p[(j*10+k)%13]+=d[j]*(c>'9'or k==int(c))
 d=[t%(10**9+7)for t in p]
print(d[5])
def main():
	list = []
	n = int(input())
	for i in range (0,n):
		ele = int(input())
		list.append(ele)
	list.sort()
	ans = int(1)
	b = 0
	for i in range (0, n):
		ans = ans * list[i]
		if int(ans) > int(1000000000000000000):
			print(-1)
			return
	print(ans)
	return

if __name__ == "__main__":
  #Run as main program
  main()

### FIXED CODE ###

def main():
	n = int(input())
	list1 = [int(t) for t in input().split()]
	list1.sort()
	ans = 1
	b = 0
	for i in range (0, n):
		ans = ans * list1[i]
		if int(ans) > int(1000000000000000000):
			print(-1)
			return
	print(ans)
	return

if __name__ == "__main__":
  #Run as main program
  main()
n, m , q = map(int, input().split())
 
l = []
for i in range(q):
  a,b,c,d = map(int, input().split())
  l.append((a,b,c,d))
max_score = 0
comb = [[1]]
while len(comb[0]) > 0:
  seed = comb.pop()
  if len(seed) == n:
    score = 0
    for j in l:
      if seed[j[1]-1]-seed[j[0]-1]==j[2]:
      
        score += j[3]
    if score > max_score:
      max_score = score
  else:
    for k in range(seed[-1], m+1):
      comb.append(seed.copy().append(k))
print(max_score)

### FIXED CODE ###

import itertools
n, m , q = map(int, input().split())

l = []
for i in range(q):
  a,b,c,d = map(int, input().split())
  l.append((a,b,c,d))
  
comb = itertools.combinations_with_replacement(range(1,m+1), n)

max_score = 0
for e in comb:
  score = 0
  for j in l:
    if e[j[1]-1]-e[j[0]-1]==j[2]:
      
      score += j[3]
  if score > max_score:
    max_score = score
print(max_score)
n=int(input())
a=[int(i) for i in inpup().split()]
cnt=0
flag=False
for i in range(1,n):
    if a[i]==a[i-1]:
        if flag:
            flag=False
        else:
            cnt+=1
            flag=True
    else:
        flag=False
print(cnt)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
cnt=0
flag=False
for i in range(1,n):
    if a[i]==a[i-1]:
        if flag:
            flag=False
        else:
            cnt+=1
            flag=True
    else:
        flag=False
print(cnt)
N , M = map(int, input().split())

def mkmap(N, M):
    mapdic = {}
    for i in range(1, M+1):
        mapdic[str(i)] = [] 
    for j in range(N):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]

print(len(roots[-1]))

### FIXED CODE ###


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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, N+1):
        mapdic[str(i)] = [] 
    for j in range(M):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]


List = [str(n+1) for n in range(N)]
check = "".join(List)
ans = 0
for i in roots[-1]:
    TF = "".join(sorted(list(i))) == check
    if TF:
        ans = ans + 1

print(ans)
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
import functions
F = sys.stdin

N, M = list(map(int,F.readline().rstrip().split()))
a_list = list(map(int,F.readline().rstrip().split()))

num = 1
while a_list[0] % 2**(num + 1) == 0:
    num += 1
def lcm(a, b):
    return (a * b) // functions.gcd(a, b)

lcm_before = 1
for a in a_list:
    if (a/(2**num)) % 2 != 1:
        print(0)
        sys.exit()

    lcm_before = lcm(lcm_before, a//2)



ans1 = M // lcm_before
ans = (ans1 + 1) // 2
print(ans)


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
import fractions
F = sys.stdin

N, M = list(map(int,F.readline().rstrip().split()))
a_list = list(map(int,F.readline().rstrip().split()))

num = 1
while a_list[0] % 2**(num + 1) == 0:
    num += 1
def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)

lcm_before = 1
for a in a_list:
    if (a/(2**num)) % 2 != 1:
        print(0)
        sys.exit()

    lcm_before = lcm(lcm_before, a//2)



ans1 = M // lcm_before
ans = (ans1 + 1) // 2
print(ans)
import sys
def main():
  S=list(input())
  T=list(input())
  lS=len(S)
  lT=len(T)
  ans=[[]*lS for _ in range(lT)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        if iS-1>=0 and iT-1>=0:
          ans[iT][iS]=ans[iT-1][iS-1]+S[iS]
        else:
          ans[iT][iS]=S[iS]
      else:
        if iS-1>=0 and (iT-1<0 or len(ans[iT][iS-1])>=len(ans[iT-1][iS])):
          ans[iT][iS]=ans[iT][iS-1]
        elif iT-1>=0 and (iS-1<0 or len(ans[iT-1][iS])>=len(ans[iT][iS-1])):
          ans[iT][iS]=ans[iT-1][iS]
  print(ans[lT-1][lS-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
def main():
  S=list(sys.stdin.readline())[:-1]
  T=list(sys.stdin.readline())[:-1]
  lS=len(S)
  lT=len(T)
  dp=[[0]*(lS+1) for _ in range(lT+1)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        dp[iT+1][iS+1] = max(dp[iT+1][iS],dp[iT][iS+1],dp[iT][iS]+1)
      else:
        dp[iT+1][iS+1] = max(dp[iT+1][iS],dp[iT][iS+1])

  iS = lS
  iT = lT
  ans = ""
  while(iS>0 and iT>0):
    if dp[iT][iS]==dp[iT-1][iS-1]:
      iS -= 1
      iT -= 1
    elif dp[iT][iS]==dp[iT][iS-1]:
      iS -= 1
    elif dp[iT][iS]==dp[iT-1][iS]:
      iT -= 1
    else:
      ans = S[iS-1]+ans
      iS -= 1
      iT -= 1
  print(ans)

if __name__ == '__main__':
  main()
from subprocess import*
with open('Main.cpp','w')as f:f.write(r"""
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y){return(x+=y)<mod?x:x-mod;}
int sub(int x,int y){return(x-=y)>= 0?x:x+mod;}
int dp[1<<21];
int n,a[21][21];
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int b=1;b<(1<<n);++b){
    int bc=__builtin_popcount(b)-1;
    for(int i=0;i<n;++i){
      if((b>>i&1)&&a[bc][i]){
        dp[b]=add(dp[b],dp[b^(1<<i)]);
      }
    }
  }
  printf("%d\n",dp[(1<<n)-1]);
}
""")
call(('g++','Main.cpp'))
call(('./a'))


### FIXED CODE ###

import subprocess as sp
import sys
 
code = r"""
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y){return(x+=y)<mod?x:x-mod;}
int sub(int x,int y){return(x-=y)>= 0?x:x+mod;}
int dp[1<<21];
int n,a[21][21];
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int b=1;b<(1<<n);++b){
    int bc=__builtin_popcount(b)-1;
    for(int i=0;i<n;++i){
      if((b>>i&1)&&a[bc][i]){
        dp[b]=add(dp[b],dp[b^(1<<i)]);
      }
    }
  }
  printf("%d\n",dp[(1<<n)-1]);
}
"""
 
with open("A.cpp","w") as f:
	f.write(code)
    
sp.Popen(['g++','-std=c++11','-O2',"A.cpp"]).communicate()
sp.Popen(['./a.out'],stdin=sys.stdin,stdout=sys.stdout).communicate()
import sys

sys.setrecursionlimit(20000)


def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


n = int(input())
A = inpl()

ans = gcd(A[0], A[1])
for a in A:
    ans = gcd(ans, a)
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(20000)


def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


n = int(input())
A = inpl()
A.sort()
ans = gcd(A[0], A[1])
for a in A:
    ans = gcd(ans, a)
print(ans)
n,m,k = map(int,input().split())
mod = 998244353
ans = 0
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = mod
N = 10**6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
for i in range(0,k+1):
  ans += m*pow(m-1,n-1-i,mod)*cmb(n-1,i,p)
  ans %= mod
print(ans)

### FIXED CODE ###

s = input()
t = input()
if len(t) != len(s)+1:
  print("No")
  quit()
if s == t[:len(s)]:
  print("Yes")
else:
  print("No")
import sys
from collections import defaultdict
r=sys.stdin.readline
X,Y=map(int,r().split())
#a=X-2b, b=Y-2a
sys.setrecursionlimit(10**6)
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
    print(0)
    exit(0)   
a=(2*Y-X)//3
b=(2*X-Y)//3
MOD=10**9+7
N=10**6
#permutation with repetition
#ex) ab, ba --> a+bCa
def pow(a,b):
    ans=1
    while b:
        if b&1:
            ans=(ans*a)%MOD
        a=(a**2)%MOD
        b=b//2
    return ans 
N=a+b
K=a
fac=[1 for _ in range(N+1)]
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
A=fac[N]
B=(fac[N-K]*fac[K])%MOD
print((A%MOD)*pow(B,MOD-2)%MOD)



### FIXED CODE ###

import sys
r=sys.stdin.readline
X,Y=map(int,r().split())
#a=X-2b, b=Y-2a
if 2*X-Y<0 or (2*X-Y)%3!=0 or 2*Y-X<0 or (2*Y-X)%3!=0:
    print(0)
    exit(0)   
a=(2*Y-X)//3
b=(2*X-Y)//3
MOD=10**9+7
#ex) ab, ba --> a+bCa
def pow(a,b):
    ans=1
    while b:
        if b&1:
            ans=(ans*a)%MOD
        a=(a**2)%MOD
        b=b//2
    return ans 
N=a+b
K=a
fac=[1 for _ in range(N+1)]
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
A=fac[N]
B=(fac[N-K]*fac[K])%MOD
print((A%MOD)*pow(B,MOD-2)%MOD)
N,K=[int(x) for x in input().split()]
S=input()
print(S[:K]+S[K].lower()+S[min(K+1,N-1):])

### FIXED CODE ###

N,K=[int(x) for x in input().split()]
S=input()
print(S[:K-1]+S[K-1].lower()+S[K:])
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    x = f()
    ans = (x//11)*2 
    remain = x%11
    add = 0
    if remain!=0:
        add = (2 if remain >6 else 1)
    
    print(ans + add)

solve()


### FIXED CODE ###

import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    x = f()[0]
    ans = (x//11)*2 
    remain = x%11
    add = 0
    if remain!=0:
        add = (2 if remain >6 else 1)
    
    print(ans + add)

solve()
n,m = map(int, input().split())

dp = [[int("inf") for _ in range(2**n)] for _ in range(m)]
dp[0][0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
    for j in range(2**n):
        jord = j | d
        
        #initialize
        if i==0:
            dp[0][d] = a
        else:
            dp[i][jord] = min(dp[i-1][jord], dp[i-1][j] + a)
            
if dp[m-1][2**n-1] == int("inf"):
    print(-1)
else:
    print(dp[m-1][2**n-1])

### FIXED CODE ###

#dpがやや特殊なので、1次元的に走査したほうがよさそう。initializeもいらないし。
n,m = map(int, input().split())

inf = 10**9

dp =[inf for _ in range(2**n)]
dp[0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    for j in range(2**n):
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
import sys

N = int(input())
C = [0]
for line in sys.stdin:
    c = int(line)
    if c[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    tree = defaultdict(list)

    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]

    def dfs(v,p,d):
        depth[v] = d
        for u in tree[v]:
            if u[0] == p:continue
            if tree[u[0]]:
                dfs(u[0],v,d+u[1])

    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict,deque
def main():
    N = int(input())
    depth = [-1 for _ in range(N)]
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    stack = deque([K])
    depth[K] = 0
    while stack:
        v = stack.popleft()
        for e in tree[v]:
            u,c = e
            if u == K:
                continue
            if depth[u] == -1:
                stack.appendleft(u)
                depth[u] = depth[v] + c

    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)

if __name__ == "__main__":
    main()
n = int(input())
dictionary = dict()
for i in range(n):
	command,data = input().split()
	if command = 'insert':
		dictionary[data] = 1
	else:
		if data in dictionary:
			print('yes')
		else:
			print('no')

### FIXED CODE ###

n = int(input())
#n = int(lines.pop())

dictionary = dict()
for i in range(n):
	command,data = input().split()
	#command,data = lines.pop().split()
	if command == 'insert':
		dictionary[data] = 1
	else:
		if data in dictionary:
			print('yes')
		else:
			print('no')