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

X, Y = map(int, input().split())

p = [[0 for i in range(Y+2)]for j in range(X+2)]
waru = 1000000007

p[0][0]=1

for y in range(Y):
    for x in range(X):
        p[x+1][y+2] += p[x][y] % waru
        p[x+2][y+1] += p[x][y] % waru

print(p[X][Y] % waru)

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    X, Y = NMI()
    if (2*Y - X)%3 or (2*X - Y)%3:
        print(0)
        exit()

    A = (2*Y - X) // 3
    B = (2*X - Y) // 3
    if A < 0 or B < 0:
        print(0)
        exit()
    print(combinations_mod(A+B, A))


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

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)

fin = np.array([N] * N, dtype=np.int64)


@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i in range(N):
        l = max(0, i - a[i])
        r = min(N - 1, i + a[i])

        b[l:r+1] += 1
    return b


for k in range(K):
    a = calc_b(a)

    if np.all(a == fin):
        break

a = [str(_) for _ in a]
print(' '.join(a))


### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

num = int(input())
a = [int(input()) for i in range(num)]
b = sorted(a, reverse=True)
for f in a:
  if max(a) == f:
    print(b[1])
  else:
    print(b[0])

### FIXED CODE ###

from heapq import nlargest

n = int(input())
a = [int(input()) for i in range(n)]
b = nlargest(2, a)
ma = max(a)
for j in a:
  if j == ma:
    print(b[1])
  else:
    print(ma)
### BUGGY CODE ###

c=list(map(int,input().split()))
bunsi=c[0]
bunbo=c[1]
n=c[2]
k=n//bunbo
d=[n]
if k!=0:
    for i in range(0,k):
        d.append(bunbo*(i+1)-1)
#dの中には候補となるxが入った
def floor(x):
    return ((bunsi*x)//bunbo)-(bunsi*(x//bunbo))
if len(d)>=2:
    print(max(floor(d[0]),floor(d[-1]),floor(d[-2])))
if len(d)==1:
    print(floor(d[0]))

### FIXED CODE ###

c=list(map(int,input().split()))
bunsi=c[0]
bunbo=c[1]
n=c[2]
k=n//bunbo
d=[n]
if k>=1:
    d.append(bunbo-1)
    d.append(bunbo*k-1)
#dの中には候補となるxが入った
def floor(x):
    return ((bunsi*x)//bunbo)-(bunsi*(x//bunbo))
if len(d)>=2:
    print(max(floor(d[0]),floor(d[-1]),floor(d[-2])))
if len(d)==1:
    print(floor(d[0]))
### BUGGY CODE ###

def solve():
    N = int(input())
    ans = []

    for i in range(N, 0, -1):
        sm = 0
        elems = []
        for k in range(i, 0, -1):
            if sm + k <= N:
                sm += k
                elems.append(k)
                if sm == N:
                    ans = elems
    print(*ans,sep='\n')

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    ans = []

    left = 0
    right = N + 1
    while right - left > 1:
        mid = (left + right) // 2
        success, elems = calcElements(mid, N)
        if success:
            ans = elems
            right = mid
        else:
            left = mid
    print(*ans,sep='\n')

def calcElements(max_value, N):
    sm = 0
    elems = []
    for k in range(max_value, 0, -1):
        if sm + k <= N:
            sm += k
            elems.append(k)
            if sm == N:
                return (True, elems)
    
    return (False, elems)

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

import itertools 

n=int(input())

L=list(map(int,input().split()))
cnt=0
for v in itertools.combinations(L,3):
    v=list(v)
    v.sort()
    if v[0]+v[1]>v[2]:
        cnt+=1
print(cnt)

### FIXED CODE ###

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

L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if L[i]+L[j]<=L[j+1]:
            continue
        if L[i]+L[j]>L[n-1]:
            cnt+=n-j-1
            continue
        left=j+1
        right=n-1
        while right-left>1:
            mid=left+(right-left)//2
            if L[mid]<L[i]+L[j]:
                left=mid
            else:
                right=mid
        cnt+=left-j
print(cnt)
### BUGGY CODE ###

a=int(input())
A=list(map(int,input().split()))
ans=1
for x in A:
  ans*=x

if ans>10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

a=int(input())
A=list(map(int,input().split()))
ans=1
if A.count(0)==0:
    for x in A:
      ans*=x
      if ans>10**18:
        break


    if ans>10**18:
      print(-1)
    else:
      print(ans)
else:
  print(0)
### BUGGY CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
i=0
#for room_i in connected_list:
    #print(room_i)
while(True):
    try:
        room_i = connected_list[i]
    except:
        break
    next_room_set = connect_dic[room_i]-next_connect_dic.keys()
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

### FIXED CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])
### BUGGY CODE ###

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

S = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="#":
            S[h][w] = 0
        else:
            S[h][w] = 1

Sh = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h][ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h][ww] = cnt

Sw = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
    se = []
    cnt = 0
    for h in range(H):
        val = S[h][w]
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh][w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh][w] = cnt


mx = 0
for h in range(H):
    for w in range(W):
        mx = max(Sh[h][w] + Sw[h][w], mx)

print(max((mx-1,0)))


### FIXED CODE ###

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

S = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="#":
            S[h][w] = 0
        else:
            S[h][w] = 1

Sh = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h][ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h][ww] = cnt

Sw = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
    se = []
    cnt = 0
    for h in range(H):
        val = S[h][w]
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh][w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh][w] = cnt


mx = 0
for h in range(H):
    for w in range(W):
        mx = max(Sh[h][w] + Sw[h][w], mx)

print(max((mx-1,0)))
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
t = []
for i in range(q):
    l,r = map(int,input().split())
    s1 = s[l-1:r]
    count = 0
    for x in range(len(s1)-1):
        if s1[x] ==  "A" and s1[x+1] == "C":
            count = count + 1
    t.append(count)
for j in range(len(t)):
    print(t[j])

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
l = [0]*(n)
for i in range(n-1):
        if s[i] == "A" and s[i+1] == "C":
                l[i+1] = l[i] + 1
        else:
                l[i+1] = l[i]  
for j in range(q):
        k,t = map(int,input().split())
        print(l[t-1] - l[k-1])
### BUGGY CODE ###

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

a.sort(reverse=True)
attack = 0
#print(min(c[1],c[0]))

for i in range(min(c[1],c[0])):
  a.pop(0)

#print(a)
for i in range(len(a)):
  attack += a[i]

print(attack)

### FIXED CODE ###

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

a.sort()
attack = 0

for i in range(c[0]-c[1]):
  attack += a[i]

print(attack)
### BUGGY CODE ###

import heapq

N, M = map(int,input().split())
jobs = [[] for i in range(10 ** 5 + 1)]
lst = []

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

ans = 0

for i in range(1,M+1):
    lst += jobs[i]
    if lst:
        heapq.heapify(lst)
        k = heapq.heappop(lst)
        ans += (-1) * k

print(ans)

### FIXED CODE ###

import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    a = sorted(a, reverse=True)
    a[0] = a[0] // 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, -tmp)
print(sum(a) * -1)
### BUGGY CODE ###

import numpy as np
N, Q = map(int, input().split())
S = input()
si = S.replace("AC","11")
si = si.translate(str.maketrans({"T":"0","G":"0","A":"0","C":"0"}))
for q in range(Q):
  l, r = map(int, input().split())
  if l>=2 and S[l-2:l]=="AC" and S[r-1:r+1]=="AC":
    print(int((np.sum(list(map(int,list(si[l-1:r]))))-2)/2))
  elif l>=2 and S[l-2:l]=="AC":
    print(int((np.sum(list(map(int,list(si[l-1:r]))))-1)/2))
  elif S[r-1:r+1]=="AC":
    print(int((np.sum(list(map(int,list(si[l-1:r]))))-1)/2))
  else:
    print(int(np.sum(list(map(int,list(si[l-1:r]))))/2))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
c = [0]
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    c.append(c[-1]+1)
  else:
    c.append(c[-1])
    
for i in range(q):
  l, r = map(int, input().split())
  print(c[r-1] - c[l-1])
### BUGGY CODE ###

def main():
    n, s = map(int, input().split())
    a = sorted([int(i) for i in input().split()])
    mod = 998244353
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 % mod + dp[i][j - ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, s = map(int, input().split())
    a = sorted([int(i) for i in input().split()])
    mod = 998244353
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 % mod + dp[i][j - ai]) % mod
    print(dp[n][s])

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

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b + 1):
	if i % x == 0:
		ans += 1
print(ans)


### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

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

prev = 1
for i in range(K):
	prev *= A[i]

for i in range(K, N):
	next = prev // A[i-K] * A[i]
	print('Yes' if next > prev else 'No')
	prev = next


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(K, N):
	print('Yes' if A[i] > A[i-K] else 'No')
### BUGGY CODE ###

def pow(x, n, p):
    ans = 1
    while n:
        if n % 2:
            ans = (ans * x) % p
        x *= x
        n >>= 1
    return ans

def abp(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        tmp = abp(a, b // 2, p)
        return (tmp * tmp) % p
    if b % 2 == 1:
        return (a * abp(a, b - 1, p)) % p

def nCr(n, r, p):
    total = 1
    for i in range(r):
        total *= (n - i) * abp(r - i, p - 2, p)
        total %= p
    return total

n, a, b = map(int, input().split())
p = 1000000007
ret = pow(2, n, p) - nCr(n, a, p) - nCr(n, b, p) - 1
print(ret % p)


### FIXED CODE ###

def abp(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        tmp = abp(a, b // 2, p)
        return (tmp * tmp) % p
    if b % 2 == 1:
        return (a * abp(a, b - 1, p)) % p

def nCr(n, r, p):
    total = 1
    for i in range(r):
        total *= (n - i) * abp(r - i, p - 2, p)
        total %= p
    return total

n, a, b = map(int, input().split())
p = 1000000007
ret = abp(2, n, p) - nCr(n, a, p) - nCr(n, b, p) - 1
print(ret % p)
### BUGGY CODE ###

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

A.sort()

pot = [A.pop()]
com = 0
while A:
    com += pot.pop()
    new = A.pop()
    pot.append(new)
    pot.append(new)
    pot.sort()

print(com)


### FIXED CODE ###

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

A.sort()
from collections import deque

pot = deque([A.pop()])
com = 0
while A:
    com += pot.pop()
    new = A.pop()
    pot.appendleft(new)
    pot.appendleft(new)

print(com)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0 for i in range(3010)] for j in range(3010)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

### FIXED CODE ###

s = input()
t = input()

dp = [[0 for i in range(3010)] for j in range(3010)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

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

from sys import stdin
input = stdin.readline
def nCr(n,r):
    return fact[n]*(inv[n-r]%M)*(inv[r]%M)
M = 1000000007
k = int(input())
s = len(input().strip())
t = k+s
fact = [1]
p25 = [1]
for i in range(1,t+1):
    fact += [(fact[-1] * i)%M]
    if i<=k:
        p25  += [(p25[-1] * 25) % M]

inv = [1]*(t+1)
inv[t] = pow(fact[t], M-2, M)
for i in range(t-1, -1, -1):
    inv[i] = inv[i+1] * (i+1) % M


res = 0
for i in range(k+1):
    res+=nCr(t,t-i)*p25[i]
    res%=M
print(res)

### FIXED CODE ###

def nCr(n,r):
    return fact[n]*(inv[n-r]%M)*(inv[r]%M)
M = 1000000007
k = int(input())
s = len(input())
t = k+s
fact = [1]
p25 = [1]
for i in range(1,t+1):
    fact += [(fact[-1] * i)%M]
    if i<=k:
        p25  += [(p25[-1] * 25) % M]

inv = [1]*(t+1)
inv[t] = pow(fact[t], M-2, M)
for i in range(t-1, -1, -1):
    inv[i] = inv[i+1] * (i+1) % M


res = 0
for i in range(k+1):
    #print(nCr(t,t-i))
    res+=nCr(t,t-i)*p25[i]
    #print(res)
    res%=M
    #print(res)
print(res)
### BUGGY CODE ###

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]
  
#print(R)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if to == Sin[cur] -1:
      continue
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

print('Yes')
for i in range(1,n):
  print(Sin[i])


### FIXED CODE ###

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

import sys

input = sys.stdin.readline
R = [[] for _ in range(n)]
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a].append(b)
  R[b].append(a)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])
### BUGGY CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
V = [v for w, v in wv]
INF = 10**10
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for v, w in enumerate(dp[N]):
    if w <= W and v > ans:
        ans = v
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p = list(map(int, input().split()))
pn = np.array(p)
v = np.array([1]*k)
c = np.convolve(pn, v, mode='same')
print((max(c)+k)/2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s = 0
rs = sum(p[0:k])
ms = rs
for i in range(1, n - k + 1):
  rs = rs - p[i-1] + p[i+k-1]
  if rs > ms:
    s = i
    ms = rs

ans = 0.0
for pp in p[s:s+k]:
  ans += (1+pp)/2
print(ans)

#for i in range(len(p)-k+1):
#  s = sum(p[i:i+k])
#  if s>m: m=s  

#c = [sum(p[i:i+k]) for i in range(len(p)-k+1)]
#print(c)
#pn = np.array(p)
#v = np.array([1]*k)
#c = np.convolve(pn, v, mode='same')
#print((max(c)+k)/2)
### BUGGY CODE ###

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

i = 1
ans = 1
if N > 1:
	while P >= i**N:
		if P % i**N == 0:
			ans = i
		i += 1
else:
	ans = P
print(ans)



### FIXED CODE ###

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

ans = 1
R = int(P**(1/N)) + 1
if N == 1:
	ans = P
elif N > 40:
	ans = 1
else:
	for l in range(R):
		if P % (R-l)**N == 0:
			ans = R-l
			break
print(ans)
### BUGGY CODE ###

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

while True:
  if abs(tmp - K) < tmp:
    tmp = abs(tmp - K)
  else:
    break
 	
print(tmp)

### FIXED CODE ###

import math

N,K = map(int,input().split())
tmp = N%K

while True:
  if abs(tmp - K) < tmp:
    tmp = abs(tmp - K)
  else:
    break
 	
print(tmp)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input().rstrip())
score = [int(input().rstrip()) for _ in range(N)]
score.sort(reverse=1)

for s in score:
    if s % 10 != 0:
        break
else:
    print(0)


for i in range(N, 0, -1):
    for c in combinations(score, i):
        if sum(c) % 10 == 0:
            continue
        else:
            print(sum(c))
            exit()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input().rstrip())
score = [int(input().rstrip()) for _ in range(N)]
score.sort(reverse=1)

s_multiple_of_10 = [s for s in score if s % 10 == 0]
if len(s_multiple_of_10) == N: print(0)
s_not_multiple_of_10 = [s for s in score if s % 10 != 0]

# combinationsでも、先に１０の倍数を除外してから処理したらどうだろう
for i in range(len(s_not_multiple_of_10), 0, -1):
    for c in combinations(s_not_multiple_of_10, i):
        if sum(c) % 10 == 0:
            continue
        else:
            print(sum(c) + sum(s_multiple_of_10))
            exit()
### BUGGY CODE ###

import re
import sys

s = sys.stdin.buffer.readline().rstrip().decode()
ans = 0

for i in range(2019, 200001*2019, 2019):
    tmp = str(i)
    if tmp in s:
        index = -1
        while True:
            index = s.find(tmp, index + 1)
            if index == -1:
                break
            ans += 1
    if int(tmp) > int(s):
        break
print(ans)


### FIXED CODE ###

import sys

s = sys.stdin.buffer.readline().rstrip().decode()
MOD = 2019
ans = [1] + [0 for i in range(MOD)]
t = 1
r = 0
for i in reversed(s):
    r = (r + int(i)*t) % MOD
    t = t*10%2019
    ans[r] += 1
print(sum([m*(m-1)//2 for m in ans]))