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

n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=((k//num)**n)%(10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=pow(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import math

x = int(input())

b = -10000

while True:
    if x+b**5 > 0:
        if math.pow((x+b**5), 0.2).is_integer():
            print(int(math.pow((x+b**5), 0.2)), b)
            exit()
        
    b += 1

### FIXED CODE ###

x = int(input())

for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i ** 5 - j ** 5 == x:
            print(i,j)
            quit()
### BUGGY CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        quit()
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            ans = -1
    
    print(ans) 
    
main(a)


### FIXED CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 
def main(a):
    if 0 in a:
        print(0)
        return
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            print(-1)
            return
    
    print(ans)
    
main(a)
### BUGGY CODE ###

import math
import copy
from functools import reduce

def gcd(*numbers):
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    return reduce(gcd, numbers)


N = int(input())
A = list(map(int,input().split()))

a_max = 0
for i in range(N):
    new_a = copy.deepcopy(A)
    new_a.pop(i)
    a_max = max(a_max,gcd(*new_a))

print(a_max)


### FIXED CODE ###

def gcd(x,y):
    if x % y == 0:
        return y
    else:
        x %= y
        return gcd(y, x)

N = int(input())
blackboard = list(map(int,input().split()))

l_gcd = [-1] * N
r_gcd = [-1] * N

for i in range(N):
    if i == 0:
        l_gcd [0] = blackboard[0]
    else:
        l_gcd[i] = gcd(l_gcd[i-1],blackboard[i])


for i in reversed(range(N)):
    if i == N - 1:
        r_gcd[N-1] = blackboard[N-1]
    else:
        r_gcd[i] = gcd(r_gcd[i+1],blackboard[i])


#左端と右端のときの値を予め比較しておく。
ans = max(l_gcd[-2],r_gcd[1])

for i in range(1,N-1):
    ans = max(ans,gcd(l_gcd[i-1],r_gcd[i+1]))
print(ans)
### BUGGY CODE ###

int1 = lambda x: int(x) - 1

N, K = map(int, input().split())
P = tuple(map(int1, input().split()))
C = tuple(map(int, input().split()))

visited = set()
cycles = []
for i in range(N):
    if i not in visited:
        cur = P[i]
        cycle = [i]
        while cur != i:
            visited.add(cur)
            cycle.append(cur)
            cur = P[cur]
        cycles.append(cycle)

ans = -float('inf')
for cycle in cycles:
    score = [0]
    for x in cycle * 2:
        score.append(score[-1] + C[x])

    # i回進めるときのスコア最大値
    lst = [0] * (min(K, len(cycle)) + 1)
    lst[0] = -float('inf')
    for i in range(1, min(K, len(cycle)) + 1):
        tmp = -float('inf')
        for j in range(len(cycle)):
            tmp = max(tmp, score[j + i] - score[j])
        lst[i] = tmp

    lap = K // len(cycle)
    if lap == 0:
        ans = max(ans,
                  max(lst))
    else:
        around_score = lst[len(cycle)]
        ans = max(ans,
                  max(lst),
                  around_score * (lap - 1) + max(lst),
                  around_score * lap + max(lst[:K % len(cycle) + 1]))
print(ans)


### FIXED CODE ###

int1 = lambda x: int(x) - 1

N, K = map(int, input().split())
P = tuple(map(int1, input().split()))
C = tuple(map(int, input().split()))

visited = set()
cycles = []
for i in range(N):
    if i not in visited:
        cur = P[i]
        cycle = [i]
        while cur != i:
            visited.add(cur)
            cycle.append(cur)
            cur = P[cur]
        cycles.append(cycle)

ans = -float('inf')
for cycle in cycles:
    l = len(cycle)
    score = [0]
    for x in cycle * 2:
        score.append(score[-1] + C[x])

    # i回進めるときのスコア最大値
    lst = [0] * (min(K, l) + 1)
    lst[0] = -float('inf')
    for i in range(1, min(K, l) + 1):
        tmp = -float('inf')
        for j in range(l):
            tmp = max(tmp, score[j + i] - score[j])
        lst[i] = tmp

    lap = K // l
    if lap == 0:
        ans = max(ans,
                  max(lst))
    else:
        around_score = lst[l]
        ans = max(ans,
                  max(lst),
                  around_score * (lap - 1) + max(lst),
                  around_score * lap + max(lst[:K % l + 1]))
print(ans)
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    wl, vl = zip(*wv)

    srs = {
        (w, -1): 0 for w in range(W+1)
    }

    def dp(w, i):
        if w - wl[i] < 0:
            return srs[(w, i-1)]
        return max(
            srs[(w - wl[i], i-1)] + vl[i],
            srs[(w, i-1)]
        )
    
    for w in range(W+1):
        for i in range(N):
            srs[(w, i)] = dp(w, i)
    
    print(srs[W, N-1])


main()


### FIXED CODE ###

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

wvs = [list(map(int, input().split())) for _ in range(N)]

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

for i, (w, v) in enumerate(wvs):
    i += 1
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j - w] + v, dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        a-=a//k+1

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        once=a//k+1
        seg=a%k
        cnt=(seg+once-1)//once
        a-=cnt*once

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")
### BUGGY CODE ###

n,m=map(int, input().split())
A=list(map(int, input().split()))
for i in range(m):
  A.sort()
  b,c=map(int, input().split())
  j=0
  while j<=b-1 and A[j]<c:
    A[j]=c
    j=j+1

print(sum(A))

### FIXED CODE ###

n,m=map(int, input().split())
A=[]
a=list(map(int, input().split()))
for i in  range(n):
  A.append([a[i], 1])
  
l=[]
for i in range(m):
  b,c=map(int, input().split())
  l.append([c,b])

A.extend(l)
A.sort()
A.reverse()
B=[]

j=0
cnt=-1
while cnt<n:
  B.extend([A[j][0]]*A[j][1])
  cnt=cnt+A[j][1]
  if cnt>=n:
    del B[n:]
  j=j+1

print(sum(B))
### BUGGY CODE ###

def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,k=n1()
p=n1()

e=[(1+x)/2 for x in p]

ans=sum(e[0:k])
tmp=ans
for i in range(1,n):
    tmp=sum(e[i:i+k])
    ans=max(tmp,ans)
print(ans)

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,k=n1()
p=n1()

e=[(1+x)/2 for x in p]

ans=sum(e[0:k])
tmp=ans
for i in range(k,n):
    tmp=tmp+e[i]-e[i-k]
    ans=max(tmp,ans)
print(ans)
### BUGGY CODE ###

def resolve():
    N, C, K = map(int, input().split())
    T = [int(input()) for _ in range(N)]
    T.sort()
    count_bus = 0
    L = len(T)

    i = 0
    while i < L:
        # print('T[{}]: {}'.format(i, T[i]))
        t = T[i]
        for j in range(1, C):
            if i+j >= L:
                i += j
                count_bus += 1
                break

            if T[i+j] <= t + K:
                pass
                if j == C-1:
                    i += j + 1
                    count_bus += 1
                    break

            else:
                count_bus += 1
                i += j
                break

    print(count_bus)


if __name__ == '__main__':
    resolve()

### FIXED CODE ###

N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

# print(T)

bus = 1
org = T[0]
_count = 0

for t in T:

    if t - org <= K and _count < C:
        _count += 1
        # print('1- t:{}, org:{}, _count:{}, bus:{}'.format(t, org, _count, bus))
    else:
        bus += 1
        org = t
        _count = 1
        # print('2- t:{}, org:{}, _count:{}, bus:{}'.format(t, org, _count, bus))

print(bus)
### BUGGY CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# 連続している最大値を求める

max_count = 0
for starti in range(len(p)):
    previous = p[starti]
    count = 1
    for i in range(starti, len(p)):
        if previous + 1 == p[i]:
            previous += 1
            count += 1

    if max_count < count:
        max_count = count

    
print(n-max_count)


### FIXED CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# 連続している最大値を求める

lengths = {}
for pn in p:
    if pn in lengths:
        lengths[pn+1] = lengths[pn] + 1
    else:
        lengths[pn+1] = 1
    
max_count = max(lengths.values())
print(n-max_count)
### BUGGY CODE ###

from itertools import permutations

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

n, m, r = input_list()
rlist = input_list()
rlist = [r-1 for r in rlist]
d = [[float('inf')]*n for i in range(n)]
for i in range(n):
    d[i][i] = 0
    
for i in range(m):
    a, b, c = input_list()
    d[a-1][b-1] = c
    d[b-1][a-1] = c

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

ans = float('inf')
for p in permutations(rlist):
    distance = 0
    for i in range(r-1):
        distance += d[p[i]][p[i+1]]

    if ans > distance:
        ans = distance

print(ans)
        


### FIXED CODE ###

from itertools import permutations

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

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

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

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()
### BUGGY CODE ###

inf=998244353


N,K=map(int,input().split())
SS=[]

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)

SS.sort()

table = [0 for k in range(N-1)] 

for s in SS:
    if s<=N-1:
        table[s-1]+=1
for i in range(N-1):
    if table[i]!=0:
        table[i]%=inf
        for s in SS:
            if i+s<N-1:
                table[i+s]+=table[i]
                #print(table,i,s)
            else:
                break
print(table[-1]%inf)


### FIXED CODE ###

inf=998244353


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

SS.sort()

table = [0 for k in range(N)] 
diff = [0 for k in range(N-1)]

table[0]=1
diff[0]=-1

for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            lef=s[0]
            rig=s[1]
            if i+lef-1<N-1:
                diff[i+lef-1]+=table[i]
            if i+rig<N-1:
                diff[i+rig]-=table[i]
    table[i+1]=table[i]+diff[i]
    table[i+1]%=inf

print(table[N-1])
### BUGGY CODE ###

n,k=map(int,input().split())
S = input()
binary = []
one = []
zero = []
tmp_z = 0
tmp_o = 0
zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")
for i,s in enumerate(S):
    if s=="0":
        tmp_z += 1
        if not zeroflag:
            one.append(tmp_o)
            tmp_o=0
            zeroflag=True
    if s =="1":
        tmp_o+=1
        if zeroflag:
            zero.append(tmp_z)
            tmp_z=0
            zeroflag=False
if tmp_z!=0:
    zero.append(tmp_z)
if tmp_o!=0:
    one.append(tmp_o)

zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")

if zeroflag:
    one = [1] + one
if saigozero:
    one.append(1)

if len(zero)<=k:
    print(len(S))
else:
    ans = 0
    
    for i in range(len(zero)-k + 1):
        if zeroflag and i==0:
            tmp = sum(zero[i:i+k])+sum(one[i:i+k+1]) -1
        elif saigozero and i==len(zero)-k:
            tmp = sum(zero[i:i+k])+sum(one[i:i+k+1]) -1
        else:
            tmp = sum(zero[i:i+k])+sum(one[i:i+k+1])
        ans = max(ans,tmp)
    print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
S = input()
binary = []
one = []
zero = []
tmp_z = 0
tmp_o = 0
zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")
for i,s in enumerate(S):
    if s=="0":
        tmp_z += 1
        if not zeroflag:
            one.append(tmp_o)
            tmp_o=0
            zeroflag=True
    if s =="1":
        tmp_o+=1
        if zeroflag:
            zero.append(tmp_z)
            tmp_z=0
            zeroflag=False
if tmp_z!=0:
    zero.append(tmp_z)
if tmp_o!=0:
    one.append(tmp_o)

zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")

if zeroflag:
    one = [1] + one
if saigozero:
    one.append(1)
    
one_sum = [0]*(len(one)+1)
zero_sum = [0]*(len(zero)+1)
for i in range(len(one)):
    one_sum[i+1] = one_sum[i]+one[i]
for i in range(len(zero)):
    zero_sum[i+1]=zero_sum[i]+zero[i]
    


if len(zero)<=k:
    print(len(S))
else:
    ans = 0
    
    for i in range(len(zero)-k + 1):
        if zeroflag and i==0:
#             tmp = sum(zero[i:i+k])+sum(one[i:i+k+1]) -1
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]-1
        elif saigozero and i==len(zero)-k:
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]-1
        else:
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]
        ans = max(ans,tmp)
    print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b,c = map(int, input().split())
    B.append(b)
    C.append(c)

m = max(max(A), max(B), max(C))+1
res = np.arange(m,dtype=int)
newA = np.zeros((m),dtype=int)


for a in A:
    newA[a] += 1

for i in range(Q):
    newA[C[i]] += newA[B[i]]
    newA[B[i]] = 0
    print(np.dot(res,newA))

### FIXED CODE ###

import numpy as np

N = int(input())
A = []
A = np.array(list(map(int, input().split())))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b,c = map(int, input().split())
    B.append(b)
    C.append(c)

m = max(max(A), max(B), max(C))+1
res = np.arange(m,dtype=int)
newA = np.zeros((m),dtype=int)


for a in A:
    newA[a] += 1

sum_r = np.dot(res,newA)


for i in range(Q):
    b = B[i]
    c = C[i]
    sum_r = sum_r - b*newA[b] + c*newA[b]
    print(sum_r)
    newA[c] += newA[b]
    newA[b] = 0
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in a:
    b.append(str(i))
    b.reverse()
print(' '.join(b))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
ans1 = a[0::2]
ans2 = a[1::2]
if n%2 == 0:
    ans2.reverse()
    b.extend(ans2)
    b.extend(ans1)
    print(*b)
else:
    ans1.reverse()
    b.extend(ans1)
    b.extend(ans2)
    print(*b)
### BUGGY CODE ###

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

L = [[0 for x in range(W)] for y in range(H)]
R = [[0 for x in range(W)] for y in range(H)]
U = [[0 for x in range(W)] for y in range(H)]
D = [[0 for x in range(W)] for y in range(H)]

for i in range(H) :
    for j in range(1,W) :
        if (A[i][j] == "#") or (A[i][j-1] == "#") :
            L[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
    
    for j in range(W-2,-1,-1) :
        if (A[i][j] == "#") or (A[i][j+1] == "#") :
            R[i][j] = 0
        else :
            R[i][j] = R[i][j+1] + 1

for j in range(W) :
    for i in range(1,H) :
        if (A[i][j] == "#") or (A[i-1][j] == "#") :
            U[i][j] = 0
        else :
            U[i][j] = U[i-1][j] + 1

    for i in range(H-2,-1,-1) :
        if (A[i][j] == "#") or (A[i+1][j] == "#") :
            D[i][j] = 0
        else :
            D[i][j] = D[i+1][j] + 1

ans = 0

for i in range(H) :
    for j in range(W) :
        calc = L[i][j] + R[i][j] + U[i][j] + D[i][j]
        ans = max(ans,calc)

ans += 1

print(ans)


### FIXED CODE ###

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

S = [input() for i in range(H)]

L = [[0 for x in range(W)] for y in range(H)]
R = [[0 for x in range(W)] for y in range(H)]
U = [[0 for x in range(W)] for y in range(H)]
D = [[0 for x in range(W)] for y in range(H)]


for i in range(H) :
    flg = 0
    for j in range(W) :
        if S[i][j] == "#" :
            flg = 1
        elif flg :
            flg = 0
        elif j == 0 :
            L[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
    
    flg = 0
    for j in range(W-1,-1,-1) :
        if S[i][j] == "#" :
            flg = 1
        elif flg :
            flg = 0
        elif j == W-1 :
            R[i][j] = 0
        else :
            R[i][j] = R[i][j+1] + 1

for j in range(W) :
    flg = 0
    for i in range(H) :
        if S[i][j] == "#" :
            flg = 1
        elif flg :
            flg = 0
        elif i == 0 :
            U[i][j] = 0
        else :
            U[i][j] = U[i-1][j] + 1
    
    flg = 0
    for i in range(H-1,-1,-1) :
        if S[i][j] == "#" :
            flg = 1
        elif flg :
            flg = 0
        elif i == H-1 :
            D[i][j] = 0
        else :
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(H) :
    for j in range(W) :
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j])

ans += 1

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

import numpy as np
N,K=map(int,input().split())
L=np.array([list(map(int, input().split()))]).reshape(-1)
M=0
M_IND=0

for i in range(len(L)-(K-1)):
  tmp = sum(L[i:i+K])
  #print(tmp)
  if M < tmp:
    M = tmp
    M_IND=i
#print(M_IND)
#for k in range(L[M_IND,M_IND+K])
ANS=0
MEMO=[0]*(max(L[M_IND:M_IND+K])+1)
MEMO_MIN=0
for i in L[M_IND:M_IND+K]:
  #print(i)
  ex = 0
  if MEMO[i] == 0:
    ex= (i+1)/2
    MEMO[i] = ex
  else:
    ex = MEMO[i]
  ANS += ex
print(ANS)


### FIXED CODE ###

def kitai(n):
  return (int(n)+1)/2

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

L=np.array([list(map(kitai, input().split()))]).reshape(-1)

from itertools import accumulate

acc = [0]+ list(accumulate(L)) # 0を忘れずに
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

N, M, K =map(int, input().split())
A = list(map(int, input().split()))
A.insert(0,0)
B = list(map(int, input().split()))  
B.insert(0,0)
len_A = len(A)
len_B = len(B)
dp = [[10**10]*len_B for _ in range(len_A)]
ans = 0
for i in range(len_A):
    for j in range(len_B):
        if i == 0 and j == 0:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = dp[i][j-1] + B[j]
            if dp[i][j] <= K and ans < i+j :
                ans = i+j
            if dp[i][j] >= K:
                break
        else:
            dp[i][j] = dp[i-1][j] + A[i]
            if dp[i][j] <= K and ans < i+j :
                ans = i+j
            if dp[i][j] >= K:
                break

print(ans)


### FIXED CODE ###

N, M, K =map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))  
sum_A = [0]
sum_B = [0]
for a in range(len(A)):
    sum_A.append(sum_A[a]+A[a])

for b in range(len(B)):
    sum_B.append(sum_B[b]+B[b])

len_A = len(sum_A)
j = len(sum_B) - 1
ans = 0
for i in range(len_A):
    a = sum_A[i]
    while True:
        if j < 0:
            break
        if a + sum_B[j] <= K:
            ans = max(ans,i + j)
            break
        j -= 1
    if j < 0:
        break

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

l=list(input())
k=int(input())
m=[0]*len(l)
for i in range(len(l)):
    var=pow(int(l[i]),5*pow(10,15))
    if(i==0):
        m[i]+=var
    if(i>=1):
        m[i]+=(m[i-1]+var)
    if(k<=m[i]):
        print(l[i])
        exit()

### FIXED CODE ###

l=list(input())
k=int(input())
m=[0]*len(l)
for i in range(len(l)):
    var=pow(int(l[i]),100)
    if(i==0):
        m[i]+=var
    if(i>=1):
        m[i]+=(m[i-1]+var)
    if(k<=m[i]):
        print(l[i])
        exit()
### BUGGY CODE ###

N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
for i in range(K//2,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
ans=0
for i in range(1,K+1):
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))

### FIXED CODE ###

N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)
### BUGGY CODE ###

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

p =  [0] * n

for i in range(n):
    if i + 1 in hole:
        p[i] = 0
    else:
        if i == 0:
            p[0] = 1
        elif i == 1:
            p[1] = p[0] + 1
        else:
            p[i] = p[i-1] + p[i-2]

print(p[n-1] % (10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int,input().split())
hole = [int(input()) for _ in range(m)]
k = 0
a, b = 0, 0
x = (10 ** 9 + 7)
for i in range(n):
    if m >= 1:
        if i + 1 == hole[k]:
            a, b = 0, a
        else:
            if i == 0:
                a = 1
            elif i == 1:
                a, b = (a + 1) % x, a % x
            else:
                a, b = (a + b) % x, a % x
        if i + 1 >= hole[k] and k < m - 1:
            k += 1
    else:
        if i == 0:
                a = 1
        elif i == 1:
            a, b = (a + 1) % x, a % x
        else:
            a, b = (a + b) % x, a % x
    
print(a)
### BUGGY CODE ###

s = input()
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            R = "".join([R, a[2]])
        else:
            F = "".join([a[2], F])

ans = "".join([F, s, R])
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

from collections import deque
d = deque()
d.extend(list(input()))
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = tuple(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            d.append(a[2])
        else:
            d.appendleft(a[2])

ans = "".join(d)
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])