Harryxun/stf_run huggingface dataset:
def f(a,d,T):
    try:
        return T[d:].index(a)+d
    except ValueError:
        return len(T)

def g(a,d,T):
    try:
        return T[:d].index(a)
    except ValueError:
        return 0

A=26

D=int(input())

C=[0]+list(map(int,input().split())) #減る満足度のベース
S=[0]*(D+1) #S[d][i] :(d+1)日目にコンテストiを開催した時の満足度

for i in range(1,D+1):
    S[i]=[0]+list(map(int,input().split()))

T=[0]
for i in range(D):
    T.append(int(input()))
            
X=0
L=[0]*(A+1)
for d in range(1,D+1):
    X+=S[d][T[d]]
    for j in range(1,A+1):
        if j!=T[d]:
            L[j]+=1
            X-=C[j]*L[j]
        else:
            L[j]=0

M=int(input())
for _ in range(M):
    d,q=map(int,input().split())
    p=T[d]
    
    Y=(f(p,d+1,T)-d)*(d-g(p,d,T))
    Z=(f(q,d+1,T)-d)*(d-g(p,d,T))

    X+=(S[d][q]-S[d][p])+Z*C[q]-Y*C[p]
    print(X)

    T[d]=q 


### FIXED CODE ###

from random import randint
A=26

D=int(input())

C=list(map(int,input().split()))

S=[0]*D
for i in range(D):
    S[i]=list(map(int,input().split()))

for j in range(D):
    print(randint(1,A))
import numpy as np
n,k = map(int,input().split())

a = np.array(input().split(),np.int)

F = np.array(input().split(),np.int)

A.sort()
F.sort()

F = F[::-1]

left = -1
right = (A * F).sum()

while (right - left) > 1:
    s = (left + right) // 2
    r = np.maximum(0, A - s // F).sum() <= k
    if r:
        right = s 
    else:
        left = s 

print(right)


### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())

A = np.array(input().split(),np.int)

F = np.array(input().split(),np.int)


A.sort()
F.sort()

F_ = F[::-1]

left = -1
right = (A * F_).sum()

while (right - left) > 1:
    s = (left + right) // 2
    r = np.maximum(0, A - s // F_).sum() <= k
    if r:
        right = s 
    else:
        left = s 

print(right)
n = (int)raw_input()
print "ABC" + (str)n

### FIXED CODE ###

n = raw_input()
print "ABC" + n
n = input()
l = list(map(int ,input().split(" ")))
 
count = 0
 
while True:
	for i in range(n):
		if l[i]%2 == 0:
			l[i] = l[i]//2
		else:
			print(count)
			exit()
	count += 1

### FIXED CODE ###

n = int(input())
l=list(map(int,input().split()))
count=0
while True:
    for i in range(n):
        if l[i]%2==0:
            l[i]=l[i]//2
        else:
            print(count)
            exit()
    count+=1
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [X[i] - Y[i] for i in range(N)]
D = filter(lambda x: x > 0, D)
print(sum(D))

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
x=0
y=0
l=[v[j]-c[j] for j in range(n)]
l.sort(reverse=True)
l=filter(lambda x:x >0,l)
print(sum(l))
import sys
input = sys.stdin.readline

def dfs(v, p=-1):
    for u in to[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u, v)
    
def main():
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
        
    for i in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
        
    dfs(0)
    
    for a in ans: print(a)

if __name__ == '__main__':
    N, Q = map(int, input().split())
    to = [[] for i in range(N)]
    ans = [0] * N
    
    main()

### FIXED CODE ###

from collections import deque

def main():
  N, Q = map(int, input().split())
  visited = [False] * (N+1)
  graph = {i:deque() for i in range(N+1)}

  for i in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

  visited[1] = True

  c = [0] * (N+1)
  for i in range(Q):
    p, x = map(int, input().split())
    c[p] += x
    
  q = [1]
  while q:
    per = q.pop()
    for child in graph[per]:
      if not visited[child]:
        visited[child] = True
        c[child] += c[per]
        q.append(child)

  for i in range(1, N+1):
    print(c[i], '', end='')

if __name__ == '__main__':
  main()
import sys
input = sys.stdin.readline
import numpy as np

from itertools import combinations_with_replacement as CwR



n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Tables = list(CwR(range(1,M+1),N))
Sum_cor = []
for Table in Tables:
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)


print(max(Sum_cor))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

from itertools import combinations_with_replacement as CwR



n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Tables = list(CwR(range(1,m+1),n))
Sum_cor = []
for Table in Tables:
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)

print(max(Sum_cor))
def cul(x,X):
    dic={0:1}
    for i in range(len(x)):
        tmp={}
        for j in dic:
            tmp[j+x[i]]=1
            tmp[j-x[i]]=1
        dic=tmp
    if X in dic: return True
    else: return False

s=list(input().split("T"))
X,Y=map(int,input().split())
x,y=[len(i) for i in s[::2]],[len(i) for i in s[1::2]]
if s[0][0]=="F": X=abs(X-x.pop(0))
Y=abs(Y)

x.sort(reverse=True)
y.sort(reverse=True)

print("Yes" if cul(x,X) and cul(y,Y) else "No")

### FIXED CODE ###

def f(s):
    return abs(int(s))

def cul(x,X):
    dic={0:1}
    for i in range(len(x)):
        tmp={}
        for j in dic:
            tmp[j+x[i]]=1
            tmp[j-x[i]]=1
        dic=tmp
    if X in dic: return True
    else: return False

s=input()
X,Y=map(int,input().split())
x,y=[],[]
d,tmp=0,0
for i in range(len(s)):
    if s[i]=="T":
        if tmp!=0:
            if d==0: x.append(tmp)
            else: y.append(tmp)
        d^=1
        tmp=0
        
    else: tmp+=1
if tmp!=0:
    if d==0: x.append(tmp)
    else: y.append(tmp)


if s[0]=="F": X=abs(X-x.pop(0))
Y=abs(Y)


print("Yes" if cul(x,X) and cul(y,Y) else "No")
N = int(input())
# [exit(0) if i ** 2 > N else print(i ** 2) if (i+1) ** 2 > N else print("", end="") for i in range(1, N)]
for i in range(1, N):
    if i ** 2 > N:
        print((i - 1) ** 2)
        break
    if i ** 2 == N:
        print(i ** 2)
        break


### FIXED CODE ###

N = list(map(str, [input() for i in range(2)]))
N = "".join(N)
print("YES") if N == N[::-1] else print("NO")
N = int(input())
for i in range(N):
	l = []
	line = raw_input()
	l.append(int(line.split()[0]))
	l.append(int(line.split()[1]))
	l.append(int(line.split()[2]))
	l.sort()
	if l[0]**2+l[1]**2==l[2]**2:
		print("YES")
	else:
		print("NO")

### FIXED CODE ###

N = int(input())
for i in range(N):
	line = input()
	l = [None]*3
	l[0] = int(line.split()[0])
	l[1] = int(line.split()[1])
	l[2] = int(line.split()[2])
	l.sort()
	if l[0]**2+l[1]**2==l[2]**2:
		print("YES")
	else:
		print("NO")
mod=10**9+7
x,y=map(int,input().split())

a=(-x+2*y)//3
b=(2*x-y)//3

f=[1]
for i in range(1,a+b+100):
    f.append(f[-1]*i%mod)

if a+2*b==x and 2*a+b==y:
    print(f[a+b]*pow(f[a]*f[b],mod-2,mod)%mod)
else:
    print(0)


### FIXED CODE ###

import sys
mod=10**9+7
x,y=map(int,input().split())

a=(-x+2*y)//3
b=(2*x-y)//3

if a<0 or b<0:
  print(0)
  sys.exit()
  
f=[1]
for i in range(1,a+b+1):
    f.append(f[-1]*i%mod)

if a+2*b==x and 2*a+b==y:
    print(f[a+b]*pow(f[a]*f[b],mod-2,mod)%mod)
else:
    print(0)
n = input()

if (n[0] == n[1] and n[1] == n[2]) or (n[2] == n[3] and n[1] == n[2]):
    print("Yes")
else
    print("No")

### FIXED CODE ###

n = input()

if (n[0] == n[1] and n[1] == n[2]) or (n[2] == n[3] and n[1] == n[2]):
    print("Yes")
else:
    print("No")
from collections import deque

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[i/2 for i in l]
if n==1:
  if (m//l[0])%2==0:
    print(int((m//l[0])/2))
  else:
    print(int((m//l[0]+1)/2))
  exit()
  
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

l=set(l)
a1=l.pop()
a2=l.pop()
g=gcd(a1,a2)
lcm=g*(a1/g)*(a2/g)
d=1

while l:
  a=l.pop()
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  

if lcm>m:
  print(0)
  exit()
for a in l:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))


### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

def lcm(a,b):
    g=math.gcd(a,b)
    return b*(a//g)
l=a[0]//2
for i in range(n):
    r=a[i]//2
    l=lcm(l,r)
for i in range(n):
    if (l//(a[i]//2))%2==0:
        print(0)
        exit()
res=m//l
print((res+1)//2)
#coding: utf-8
S = input()
year = 19
month = 12
mae, ushiro = S[:2], S[2:]
if 0 < mae <= month and 0 < ushiro <= month:
	print("AMBIGUOUS")
elif 0 < mae <= month and 0 < ushiro <= year:
	print("MMYY")
elif 0 < mae <= year and 0 < ushiro <= month:
	print("YYMM")
else:
	print("NA")

### FIXED CODE ###

#coding: utf-8
S = input()
year = 99
month = 12
mae, ushiro = int(S[:2]), int(S[2:])
if 0 < mae <= month and 0 < ushiro <= month:
	print("AMBIGUOUS")
elif 0 < mae <= month and 0 <= ushiro <= year:
	print("MMYY")
elif 0 <= mae <= year and 0 < ushiro <= month:
	print("YYMM")
else:
	print("NA")
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k == 0:
        break    
    if a[A[i][0]] ==0:
        a[A[i][0]] = 1
        eat.append(A[i][1])
        k -= 1
    else:
        noteat.append(A[i][1])
ans = [0 for i in range(min(K-k,len(noteat))+1)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat))):
#    if pow(K-k,2)+eat[-i] < pow(K-k-i,2)+noteat[k:][i-1]:
    ans[i] = ans[i-1]-(pow(K-k,2)+eat[-i]) +(pow(K-k-i,2)+noteat[k:][i-1])
#    else:
#        break
print(max(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k+i-1])

print(max(ans))
N = int(input())
D = []
for _ in range(N):
    a,b,c = map(int, input().split())
    D.append([a,b,c])

def dfs(n, activity):#n日目にactivityを選んだ場合の最大幸福
    if n==1:
        ans = 0
        for i in range(3):
            if i!=activity:
                ans = max(ans, D[1][activity]+D[0][i])
        return ans
    ans = 0
    for i in range(3):
        if i!=activity:
            ans =max(ans, D[n][activity]+dfs(n-1, i))
    return ans
ans = 0
for i in range(3):
    ans = max(ans, dfs(N-1, i))
print(ans)


### FIXED CODE ###

N = int(input())

vacation = []

for i in range(N):
    a,b,c = map(int, input().split())

    vacation.append([a,b,c])

dp = []*N

for i in range(N):
    dp.append([0, 0, 0])

dp[0][0]=vacation[0][0]
dp[0][1]=vacation[0][1]
dp[0][2]=vacation[0][2]

for i in range(0, N-1, 1):

    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][j] = max(dp[i+1][j], dp[i][k]+vacation[i+1][j])

print(max(dp[N-1]))
s = input()

ans1 = (("S" in s) and ("N" in s)) or (("S" not in s) & ("N" not in s))
ans2 = (("E" in s) and ("W" in s)) or (("E" not in s) & ("W" not in s)

print("Yes" if ans1 and ans2 else "No")

### FIXED CODE ###

S = input()

NS = (("S" in S) & ("N" in S)) | (("S" not in S) & ("N" not in S))
EW = (("E" in S) & ("W" in S)) | (("E" not in S) & ("W" not in S))

print("Yes") if NS & EW else print("No")
n.m=map(int,input().split())
if n==m:
  print('Yes')
  
else:
  print('No')

### FIXED CODE ###

n,m=map(int,input().split())
if n==m:
  print('Yes')
  
else:
  print('No')
l, r = map(int, input().split())
res = 2018

if r-l > 2018:
    print(0)
    eixt()
else:
    for i in range(l, r):
        for j in range(i+1, r+1):
            res = min(res, (i*j)%2019)
print(res)

### FIXED CODE ###

l, r = map(int, input().split())
res = 2018

if r-l > 2018:
    print(0)
    exit()
else:
    for i in range(l, r):
        for j in range(i+1, r+1):
            res = min(res, (i*j)%2019)
print(res)
S=''
if  S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()

if  S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")
x = list(map(int,input().split()))

for i in x:
	IF x[i] == 0:
    	print(i+1)
    ELSE:
    	pass

### FIXED CODE ###

x = list(map(int,input().split()))
 
for i in range(len(x)):
  if x[i] == 0:
    print(i+1)
    break
l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))

if l[1] == 1:
  print('1')
else:
  print('0')

### FIXED CODE ###

l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))

if l2[1] == 1:
  print('1')
else:
  print('0')
#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np

def solve(NS):
    N = NS[0]
    S = NS[1:]
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    return dp.max()

def main():
    NS = np.array([int(input())] + [ord(_) for _ in input()])
    print(solve(NS))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
import sys
import numpy as np
import copy

fline = input().rstrip().split(' ')
N, Q = int(fline[0]), int(fline[1])

list = []
for i in range(N):
    tlist = []
    line = input().split(' ')
    tlist = [line[0], line[1]]
    #print(tlist)
    list.append(tlist)

#print(list)
current = 0
while len(list) != 0:
    if int(list[0][1]) <= Q:
        current += int(list[0][1])
        print(list[0][0] + " " + str(current))
        del list[0]
    else:
        list[0][1] = str((int)(list[0][1])-Q)
        list.append(list[0])
        del list[0]
        current += Q
    #print(list)



### FIXED CODE ###

import sys
#import numpy as np
import copy

fline = input().rstrip().split(' ')
N, Q = int(fline[0]), int(fline[1])

list = []
for i in range(N):
    tlist = []
    line = input().split(' ')
    tlist = [line[0], line[1]]
    #print(tlist)
    list.append(tlist)

#print(list)
current = 0
while len(list) != 0:
    if int(list[0][1]) <= Q:
        current += int(list[0][1])
        print(list[0][0] + " " + str(current))
        del list[0]
    else:
        list[0][1] = str((int)(list[0][1])-Q)
        list.append(list[0])
        del list[0]
        current += Q
    #print(list)
N,X = (int(x) for x in input().split())
L = [int(x) for x in input().split()]
s = 0
i = 0
while (s <= X):
  if i > N:
    print(N)
    quit()
  else:
    s = s + L[i]
    i = i + 1
print(i)



### FIXED CODE ###

N,X = (int(x) for x in input().split())
L = [int(x) for x in input().split()]
s = 0
i = 0
while (s <= X):
  if i >= N:
    print(N+1)
    quit()
  else:
    s = s + L[i]
    i = i + 1
print(i)
s = list(input())
n = len(s)
#print(n)
k,g=[],[]
for i in range(n):
    if i%2==0:
        k.append(s[i])
    else:
        g.append(s[i])
#print(k)
#print(g)
for j in k:
    if j == 'L':
        print('No')
        break

else:
    for l in g:
        if l == 'R':
            print('No')
            break
    else:
        print('Yes')
        break

### FIXED CODE ###

s = list(input())
n = len(s)
#print(n)
k,g=[],[]
for i in range(n):
    if i%2==0:
        k.append(s[i])
    else:
        g.append(s[i])
#print(k)
#print(g)
for j in k:
    if j == 'L':
        print('No')
        break

else:
    for l in g:
        if l == 'R':
            print('No')
            break
    else:
        print('Yes')
n =  int(raw_input())
B = map(int, raw_input().split())
print sum(B) - sum([abs(B[i] - B[i-1]) for i in xrange(1, n)])

### FIXED CODE ###

n =  int(raw_input())
B = map(int, raw_input().split())
B = [1000000] + B + [1000000]
print sum(min(B[i-1], B[i]) for i in range(1, n+1))
MOD = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())

# f(r,c) = (r+c)_C_c

n = 200100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    temp = [nCr(k,c) for k in range(c+1,r+c+2)]
    return sum(temp) % MOD
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)


### FIXED CODE ###

MOD = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())

n = 2000100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    return nCr(r+c+2,c+1)-1
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)
n, m = map(int, input().split())

ac = 0
ans = [True] * n
wa = [0] * n

for i in range(m):
    question_number, result = input().split()
    num = int(question_number) - 1
    if result == 'AC' and ans[num]:
        ans[num] = False
        ac += 1
    elif result == 'WA' and ans[num]:
        wa[num] += 1

wa_sum = 0

for wa_num in wa:
    if not ans[num]:
        wa_sum += wa_num 

print(ac, wa_sum)

### FIXED CODE ###

n, m=map(int,input().split())
ac = 0
ans=[True] * n
wa=[0] * n

for i in range(m):
    question, result=input().split()
    num = int(question) - 1
    if result == "AC" and ans[num]:
        ans[num]=False
        ac+=1
    # WAかつACされていない場合
    elif result == "WA" and ans[num]:
        wa[num] += 1
 
wa_sum = 0

for i in range(n):
    # 問題がACされている場合、その問題番号のWA回数を足す
    if not ans[i]:
        wa_sum += wa[i]
 
print(ac, wa_sum)
n=int(input())
al=[chr(ord('a') + i) for i in range(26)]
sakai=[]
k=0
for i in range(10):
  k+=26**(i+1)
  sakai.append(k)

if n<=26:
  n-=1
  u=1
elif n>sakai[9]:
  n-=sakai[9]+1
  u=11
for i in range(9):
  if (sakai[i]<n<=sakai[i+1]):
    n-=sakai[i]+1
    u=i+2

def base(n):
  ans=[]
  while(n>26):
    r=n%26
    n=(n-r)//26
    ans.append(r)
  ans.append(n)
  return ans


p=base(n)



if u-len(p)>0:
  ans_3='a'
  if u-len(p)>1:
    for j in range(u-len(p)-1):
      ans_3+='a'
    
for i in range(len(p)):
  if i==0:
    ans_2=al[p[len(p)-i-1]]
  elif i==len(p)-1:
    ans_2=ans_2+al[p[len(p)-i-1]]
  else:
    ans_2=ans_2+al[p[len(p)-i-1]]
if u-len(p)>0:
  print(ans_3+ans_2)
else:
  print(ans_2)
               
    

### FIXED CODE ###

n=int(input())
al=[chr(ord('a') + i) for i in range(26)]
sakai=[]
k=0
for i in range(10):
  k+=26**(i+1)
  sakai.append(k)

if n<=26:
  n-=1
  u=1
elif n>sakai[9]:
  n-=sakai[9]+1
  u=11
for i in range(9):
  if (sakai[i]<n<=sakai[i+1]):
    n-=sakai[i]+1
    u=i+2

def base(n):
  ans=[]
  while(n>=26):
    r=n%26
    n=(n-r)//26
    ans.append(r)
  ans.append(n)
  return ans


p=base(n)

if u-len(p)>0:
  ans_3='a'
  if u-len(p)>1:
    for j in range(u-len(p)-1):
      ans_3+='a'
    
for i in range(len(p)):
  if i==0:
    ans_2=al[p[len(p)-i-1]]
  else:
    ans_2=ans_2+al[p[len(p)-i-1]]
if u-len(p)>0:
  print(ans_3+ans_2)
else:
  print(ans_2)
r = int(intput())
if r < 1200:
  print("ABC")
elif r < 2800:
  print("ARC")
else:
  print("AGC")

### FIXED CODE ###

a = int(input())
print("AGC" if a >= 2800 else "ARC" if a >= 1200 else "ABC")
def main(n, a):
    ans = 0
    for i, j in permutations(a, 2):
        ans = max(ans, i - j)

    print(ans)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    main(n, a)


### FIXED CODE ###

from itertools import permutations


def main(n, a):
    ans = 0
    for i, j in permutations(a, 2):
        ans = max(ans, i - j)

    print(ans)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    main(n, a)
s = str(input())

s = [_ for _ in s]
for i in range(0, len(s)-1):
    print(s)
    if i+2 <= len(s)-1:
        if s[i] == s[i+1]:
            s[i+1] = ''.join([s[i+1], s.pop()])

if s[-1] == s[-2]:
    print(len(s) - 1)
else:
    print(len(s))

### FIXED CODE ###

s = str(input())

j = 0
count = len(s)

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if j+1 <= len(s)-1:
        if s[j] == s[j+1]:
            j = j + 3
            count -= 1
        else:
            j = j + 1
            continue

print(count)
# import math
# import bisect
# import heapq
# from collections import deque
# import numpy as np

# a,b,c = map(int, input().split())
# n = int(input())
# a = list(map(int,input().split()))
s,t = input().split()
a,b = map(int, input().split())
u = int(input())
if u == s: print(a-1,b)
else: print(a,b-1)




### FIXED CODE ###

# import math
# import bisect
# import heapq
# from collections import deque
# import numpy as np

# a,b,c = map(int, input().split())
# n = int(input())
# a = list(map(int,input().split()))
s,t = input().split()
a,b = map(int, input().split())
u = input()
if u == s: print(a-1,b)
else: print(a,b-1)
S=int(input())

def f(n): 
      
    # single line to find factorial 
    return 1 if (n==1 or n==0) else n * factorial(n - 1);

possibles=1
biggest_sub=S//3
for i in range(2,biggest_sub+1):
	left=S-3*i
	possibles+=(f(left+i-1)/f(i-1)/f(left))
n=10**9+7
print(possibles%n)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def cmb(n,r):
    if n-r < r: r = n-r
    if r == 0: return 1
    denominator = 1                       #分母
    numerator = 1                         #分子
    for i in range(r):
        numerator *= n-i
        numerator %= Q
        denominator *= i+1
        denominator %= Q
    return numerator*pow(denominator, Q-2, Q)%Q
 
def main():
    S = int( input())
    ans = 0
    for i in range(1, S//3+1):
        t = S - i*3
        ans += cmb(t+i-1,i-1)
        ans %= Q
    print(ans)
        
if __name__ == '__main__':
    main()