Harryxun/stf_run huggingface dataset:
MOD = 10**9+7
fac = [1, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * pow(fac[r], mod-2, mod) * pow(fac[n-r], mod-2, mod) % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def g(x, y):
    return ((y+2) * modcmb(x+y+2, x, MOD) - (x+1)) * pow(x+1, MOD-2, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = g(r2, c2) - g(r1-1, c2) - g(r2, c1-1) + g(r1-1, c1-1)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 0
    for i in range(2,d-1):
        ans += i*(i-1)//2
    ans *= 9**3
    ans += (int(str(n)[0]) - 1) * 9**2 * (d-1)*(d-2) // 2
    ans += K2(int(str(n)[1:]))
    return ans


def main():
    N = int(input())
    K = int(input())

    if K == 1:
        print(K1(N))

    if K == 2:
        if N < 10:
            print(0)
            exit()
        print(K2(N))

    if K == 3:
        if N < 100:
            print(0)
            exit()
        print(K3(N))



if __name__ == "__main__":
    main()
import sys


sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

### FIXED CODE ###

import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [1]*(N+1)
for _ in range(M):
    has_broken[int(input())] = 0

dp = [1]*(N+1)
dp[1] = 1 if has_broken[1] == 1 else 0
MOD = 10**9+7
for i in range(2, N+1):
    dp[i] = has_broken[i]*(dp[i-1] + dp[i-2])

print(dp[N]%MOD)
_,k=map(int,input().split())
print(sum(sorted(list(map(int,input(),split())))[:k]))

### FIXED CODE ###

_,k=map(int,input().split())
print(sum(sorted(list(map(int,input().split())))[:k]))
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    import math
    def lcm(x, y):
        return (x * y) // math.gcd(x, y)
    print(lcm(2,n))
resolve()

### FIXED CODE ###


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

def resolve():
    import fractions
    n=int(input())
    print(n * 2 // fractions.gcd(n, 2))
resolve()
a,b = input().split()
if a*b%2==1:
    print("Odd")
else:
    print("Even")

### FIXED CODE ###

a,b = map(int,input().split())
if a*b%2==1:
    print("Odd")
else:
    print("Even")
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	break

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass

### FIXED CODE ###

from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass
N, T = map(int,input())
tmp=10000
ans=0

for i in range(N):
  c, tt==map(int,input())
  if tt <= T:
    tmp=min(c,tmp)
    if c==ans:
      ans=i

if ans==0:
  print('TLE')
else:
  print(ans)

### FIXED CODE ###

N, T = list(map(int, input().split()))
ans=10000

for i in range(N):
  c, tt=list(map(int, input().split()))
  if tt <= T:
    ans=min(c,ans)

if ans==10000:
  print('TLE')
else:
  print(ans)
import math
a,b = map(int,input().split())
ans = (a * b) // math.gcd(a,b)
print(ans)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
ans = (a * b) // fractions.gcd(a,b)
print(ans)
N, K = map(int, input().split())
lis = list(map(int, input().split()), N)
count = 0
for i in range(N):
    if lis[i] >= K:
        count += 1
print(count) 

### FIXED CODE ###

N, K = map(int, input().split())
lis = list(map(int, input().split()))
count = 0
for i in range(N):
    if lis[i] >= K:
        count += 1
print(count)
from itertools import combinations

n = int(input())
d = mapt(int, input().split(" "))

print(sum(d[a]*d[b] for a, b in combinations(range(n), 2)))

### FIXED CODE ###

from itertools import combinations

def mapt(fn, *args):
    return tuple(map(fn, *args))

n = int(input())
d = mapt(int, input().split(" "))

print(sum(d[a]*d[b] for a, b in combinations(range(n), 2)))
N, W = map(int, input().split())
X = [0] + [-1] * 110000
ma = 0
for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(len(X)-1, -1, -1):
        if X[j] >= 0:
            if X[j] + w <= W:
                if X[j+v] < 0:
                    # print(j+v, "->", X[j]+w)
                    X[j+v] = X[j]+w
                    ma = max(ma, j+v)
                else:
                    X[j+v] = min(X[j+w], X[j]+w)
                # print(X[:100])

print(ma)

### FIXED CODE ###

N, W = map(int, input().split())
X = [0] + [-1] * 110000
ma = 0
for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(len(X))[::-1]:
        if X[j] >= 0:
            if X[j] + w <= W:
                if X[j+v] < 0:
                    X[j+v] = X[j]+w
                    ma = max(ma, j+v)
                else:
                    X[j+v] = min(X[j+v], X[j]+w)

print(ma)
import math
HW = input().split()
H = int(HW[0])
W = int(HW[1])
print(math.ceil(H*W/2)) 








### FIXED CODE ###

K = int(input())
x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[K-1])
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k:
        if j == len(neg) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)




### FIXED CODE ###

n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
elif neg_cnt == n and k % 2 == 1:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[v]), reverse=True)
    pos.sort(key=lambda v: abs(arr[v]), reverse=True)


    if k % 2:
        res = arr[pos[0]]
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    while i + j < k:
        res *= arr[pos[i]]
        i += 1
        res %= modulo

    print(res)
N,K= map(int,input().split())
D = list(map(int,input().split()))
from itertools import accumulate
acc = [0]+list(accumulate(D, lambda x,y:x+y))
mx = 0
for k in range(K+1): # k 回とる
    rest = K-k # rest回まで捨てることができる
    for l in range(1, min(k+1, N)): # 左から何個とるか
        r = k-l
        left = acc[l]
        right = acc[N]-acc[N-r]
        tmp = left+right
        tmpl = D[:l]
        tmpr = D[N-r:N]
        minus = sorted([i for i in tmpl+tmpr if i < 0])
        tmp -= sum(minus[:rest])
        mx = max(mx, tmp)
print(mx)

### FIXED CODE ###

N,K= map(int,input().split())
D = list(map(int,input().split()))
from itertools import accumulate
acc = [0]+list(accumulate(D, lambda x,y:x+y))
mx = 0
for k in range(min(K+1, N+1)): # k 回とる
    rest = K-k # rest回まで捨てることができる
    for l in range(min(k+1, N+1)): # 左から何個とるか
        r = k-l
        left = acc[l]
        right = acc[N]-acc[N-r]
        tmp = left+right
        tmpl = D[:l]
        tmpr = D[N-r:N]
        minus = sorted([i for i in tmpl+tmpr if i < 0])
        tmp -= sum(minus[:rest])
        mx = max(mx, tmp)
if K > N:
    tmp = acc[-1]
    rest = K - N
    minus = sorted([i for i in D if i < 0])
    tmp -= sum(minus[:rest])
    mx = max(mx, tmp)
print(mx)
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10000)

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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)
    
dp = [[0] * W for _ in range(H)]

def rec(i, j):
    if field[i][j] == 1:
        return 0
    
    if dp[i][j] != 0:
        return dp[i][j]
        
    dp[i][j] = H + W
        
    min_dist = H + W
    if i > 0:
        min_dist = min(min_dist, rec(i-1, j) + 1)
    if i < H - 1:
        min_dist = min(min_dist, rec(i+1, j) + 1)
    if j > 0:
        min_dist = min(min_dist, rec(i, j-1) + 1)
    if j < W - 1:
        min_dist = min(min_dist, rec(i, j+1) + 1)
        
    dp[i][j] = min_dist
    
    return min_dist
    
    
for i in range(H):
    for j in range(W):
        rec(i, j)
     
print(max([max(temp_dp) for temp_dp in dp]))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque

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

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)
a=int(input())
b=list(input())
c=0
d=0
for i in range(a):
  if b[i]=="A":
    d+=1
  
    if d==1 and b[i+1]=='B':
      
        
      d+=1
      if d==2 and b[i+2]='C':
          
          
        
        
          d=0
          c+=1
  else:
    d=0
        
      
print(c)


### FIXED CODE ###

n=int(input())
s=list(input())
d=0
for i in range(n):
  if n-(i+1)>=2:
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      d+=1
  else:
    pass
print(d)
n = int(input())
def F(n):
    if n < 2:
        return 1
    return n*F(n-2)
i = 0
f = F(n)
while f%2==0:
    f=f/2
    i += 1

j = 0
while f%5==0:
    f=f/5
    j += 1
print(min(i,j))

### FIXED CODE ###

N = int(input())
n = N
count = 0
i = 0
if n%2 == 0:
    while n >= 10*(5**i):
        count += n//(10*(5**i))
        n = N
        i += 1
    print(count)
else:
    print(count)
H, W = map(int, input().split())
M = ['.' * (W+2)]
for _ in range(H):
    M.append('.' + input() + '.')
M.append('.' * (H+2))
flag = True
for i in range(1, H+1):
    for j in range(1, W+1):
        if M[i][j] == '#':
            if '#' not in (M[i+1][j], M[i][j+1], M[i-1][j], M[i][j-1]):
                flag = False
                break
    if flag == False:
        break
if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

H, W = map(int, input().split())
M = ['.' * (W+2)]
for _ in range(H):
    M.append('.' + input() + '.')
M.append('.' * (W+2))
flag = True
for i in range(1, H+1):
    for j in range(1, W+1):
        if M[i][j] == '#':
            if '#' not in (M[i+1][j], M[i][j+1], M[i-1][j], M[i][j-1]):
                flag = False
if flag:
    print('Yes')
else:
    print('No')
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7


ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

cnt=0
b=[ans//a[i] for i in range(n)]
print(sum(b)%mod)

### FIXED CODE ###

import sys
from collections import deque
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

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

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

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

    return arr

# print(factorization(12))
for i in range(n):
    tmp=factorization(a[i])
    for j in range(len(tmp)):
        if not tmp[j][0] in dic:
            dic[tmp[j][0]]=tmp[j][1]
        else:
            dic[tmp[j][0]]=max(dic[tmp[j][0]],tmp[j][1])
l=1
for i in dic.keys():
    l*=i**dic[i]
    l%=mod
# print(l)
ans=0
for i in range(n):
    ans+=l*pow(a[i],mod-2,mod)
    ans%=mod
print(ans)
N = int(input())
s = [int(input()) for _ in range(N)]
ans = sum(s)
if ans % 10 != 0:
    print(ans)
else:
    for s_i in s:
        if s_i % 10 != 0:
            ans -= s_i
            print(ans)
            break
    else:
        print(0)


### FIXED CODE ###

A, B = map(int, input().split())
if A + B >= 10:
    print('error')
else:
    print(A + B)
x=list(int(input()))
print(x)

if x[-1] = "2","4","5","7","9":
	y="hon"
elif x[-1] ="0","1","6","8":
	y="pon"
else:
	y="bon"

print(y)


### FIXED CODE ###

x=str(input())
y = x[-1]


if y == "3":
	 	 z="bon"
elif y == "0":
	z="pon"
elif y == "1":
	z="pon"
elif y == "6":
	z="pon"
elif y =="8":
	z="pon"
else:
	z="hon"

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

def multi_lst(lst):
    ans = lst[0]
    for i in range(1, len(lst)):
        ans *= lst[i]
    
    return ans
if a.index(0):
    print(0)
else:
    ans = multi_lst(a)
    
if ans <= 10**18:
    print(ans)
else:
    print('-1')

### FIXED CODE ###

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

try:
    idx = a.index(0)
    print(0)

except ValueError:

    ans = a[0]
    for i in range(1, len(a)):
        ans *= a[i]
        if ans > 10**18:
            print('-1')
            exit()

    print(ans)
n = int(input())
lst = list(map(int, input().split()))

start = 0
end = 1
count = n
while start < n-1:
    s = lst[start]
    next_num = lst[end]
    while s + next_num == s ^ next_num:
        count += 1
        s = s + next_num
        end += 1
        next_num = lst[end]
        if end == n:
            break
    start += 1
    end = start + 1
print(count)

### FIXED CODE ###

import itertools

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

accum_xor = []
s = 0
for i in lst:
    s = s ^ i
    accum_xor.append(s)

accum_lst = list(itertools.accumulate(lst))

def bisearch(start, n, accum_xor, accum_lst):
    low = start
    high = n
    while True:
        i = (low+high)//2
        if start == 0:
            if accum_xor[i] == accum_lst[i]:
                low = i
            else:
                high = i
        else:
            if accum_xor[start-1] ^ accum_xor[i] == accum_lst[i] - accum_lst[start-1]:
                low = i
            else:
                high = i
        if high - low <= 1:
            if start == 0:
                if accum_xor[high] == accum_lst[high]:
                    flg = True
                else:
                    flg = False
            else:
                if accum_xor[start-1] ^ accum_xor[high] == accum_lst[high] - accum_lst[start-1]:
                    flg = True
                else:
                    flg = False
            break
    return high if flg else low

s = 0
for i in range(n):
    a = bisearch(i, n-1, accum_xor, accum_lst) - i + 1
    s += a
print(s)
S = input()
count = 0
i = 0
while i < len(S)-2:
    if S[i] == S[i+1]:
        i +=3
        count += 2  
    else:
        i +=1
        count += 1
if S[i] == S[i+1]:
    count += 1
else:
    count += 2
print(count)

### FIXED CODE ###

S = input()
count = 1
strings = []
strings.append(S[0])
stack = ''
for s in S[1:]:
    stack += s
    if strings[-1] == stack:
        continue
    else:
        strings.append(stack)
        stack = ''
        count+=1    

print(count)
from fractions import gcd

def ceil(a, b):
  return -(-a//b)

a, b, c, d = map(int, input().split())
if c == 1:
  print(0)
  sys.exit()
cd_lcm = c*d//gcd(c, d)
c_left, c_right = ceil(a,c), b//c
d_left, d_right = ceil(a,d), b//d
cd_left, cd_right = ceil(a,cd_lcm), b//(cd_lcm)
cv, dv, cdv = c_right - c_left + 1, d_right - d_left + 1, cd_right - cd_left + 1
print((b - a + 1) - (cv + dv - cdv))

### FIXED CODE ###

import sys
from math import ceil
from fractions import gcd

a, b, c, d = map(int, input().split())
if c == 1:
  print(0)
  sys.exit()
cd_lcm = c*d//gcd(c, d)
c_left, c_right = ceil(a/c), b//c
d_left, d_right = ceil(a/d), b//d
cd_left, cd_right = ceil(a/cd_lcm), b//(cd_lcm)
cv, dv, cdv = c_right - c_left + 1, d_right - d_left + 1, cd_right - cd_left + 1
print((b - a + 1) - (cv + dv - cdv))
import sys

for l in sys.stdin:
  a, p = l.rstrip('\n').split(' ')
pies = (int(a) * 3 + p) //2
print(pies)

### FIXED CODE ###

import sys

for l in sys.stdin:
  a, p = l.rstrip('\n').split(' ')
pies = (int(a) * 3 + int(p)) //2
print(pies)
r,c = map(int,raw_input().split())
matrix = [0 for i in range(r)]
for i in range(r):
    matrix[i] = map(int,raw_input().split())
    a = 0

    for j in range(c):
        a += matrix[i][j]
    matrix[i].append(a)
    for j in range(c+ 1):
        print matrix[i][j],

### FIXED CODE ###

while True:
    n,x = map(int,raw_input().split())
    if n == 0 and x == 0:
        break
    num = 0

    for a in range(1,n-1):
        for b in range(a+1,n):
            for c in range(b+1,n+1):
                if a + b+ c == x:
                    num += 1
    print num
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    arr=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    println(arr[parseInt(readline())])
end
main()

### FIXED CODE ###

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[int(input())-1])
L = [int(i) for i in input().split()]<
<
if (L.count(5) == 2 and L.count(7) == 1):<
    print("YES")<
else:<
    print("NO")<

### FIXED CODE ###

L = [int(i) for i in input().split()]

if (L.count(5) == 2 and L.count(7) == 1):
    print("YES")
else:
    print("NO")
h = int(input())

def count(h):
    if(h==0):
        return 0
    if(h==1):
        return 1
    return 1 + 2*count(h/2)
    
print(count(h))


### FIXED CODE ###

h = int(input())

def count1(h):
    if(h==0):
        return 0
    if(h==1):
        return 1
    return 1 + 2*count1(h//2)
    
print(count1(h))
def main():
    N, K = map(int, input().split())
    A    = [int(i)-1 for i in input().split()]

    visited_town = []
    current_town = 0
    loop_flg     = False
    visited_town.append(current_town)
    set_visted_town = set(visited_town)
    for i in range(K):
        current_town = A[current_town]
        if current_town in set_visted_town:
            visited_town.append(current_town)
            loop_flg = True
            break
        visited_town.append(current_town)
        set_visted_town.add(current_town)


    if loop_flg:
        loop_start = visited_town.index(current_town)
        loop_end   = len(visited_town) - 1
        loop_length = loop_end - loop_start
        last_index = (K-loop_start)%loop_length
        current_town = visited_town[loop_start+last_index]

    print(current_town+1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

S = input()
T = input()

if S == T[:-1]:
    print('Yes')
else:
    print('No')
import sys
a,b,c = map(lambda x: int(x), input().split())
k = int(input())

for _ in range(k):
    if b <= a:
        b = 2 * b
        continue
    if c <= b:
        c = 2 * c
        continue
    print('Yes')
    sys.exit()
    
if (a < b) & (b < c):
    print('Yes')
    sys.exit()
print('No')

### FIXED CODE ###

print(10 - int(input())//200)
N,L=input().split()
N=int(N)
a=[]
for i in range(N):
    s=input()
    a.append(s)
a.sort()
for i in range(N):
    print(a[i],end='')
    


### FIXED CODE ###

a=input().split()
a.sort()
if a[0]=='5' and a[1]=='5' and a[2]=='7':
    print("YES")
else:
    print("NO")
n=int(input())
s=input()
l=list(s)
newcome=[]
alp=[chr(ord('A') + i) for i in range(26)]
for i in l:
  a=alp.index(i)
  if (a+n)<=26:
    t=alp[a+n]
  else:
    t=alp[a+n-26]
  newcome.append(t)
print("".join(newcome))

### FIXED CODE ###

n=int(input())
s=input()
l=list(s)
newcome=[]
alp=[chr(ord('A') + i) for i in range(26)]
for i in l:
  a=alp.index(i)
  if (a+n)<26:
    t=alp[a+n]
  else:
    t=alp[a+n-26]
  newcome.append(t)
print("".join(newcome))