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

from math import gcd

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

def createPrimeList(N, isTable=True):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

primeList = createPrimeList(10**5, False)
def primeFactorization2(N):
    primes = set()
    for p in primeList:
        if N % p == 0:
            primes.add(p)
    return primes

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    P = set()
    for a in A:
        for p in primeFactorization2(a):
            if p in P:
                return False
            P.add(p)
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            ret[N] += 1
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] >= 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

if isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

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

for i, value in enumerate(a):
    print(a.count(i+1))
print('0')


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*len(a)

for i, value in enumerate(a):
    b[value-1] += 1

for j in b:
    print(j) 

print('0')
### BUGGY CODE ###


n = int(input())

s = {}
i = 0
while n > i:
    s_tmp = input()
    if s.get(s_tmp):
        s[s_tmp] += 1
    else:
        s.setdefault(s_tmp, 1)
    i += 1
    
max_k_list = [kv[0] for kv in s.items() if kv[1] == max(s.values())]
max_k_list.sort()

for i in max_k_list:
    print(i)

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s).most_common()
ans = [k for k, v in c if c[0][1] == v]
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

i=0
print(i)
ss=input()
if ss == "Vacant":
    exit()
else:
    i=(N-1)//2
    count=4
    while True:
        print(i)
        s=input()
        if s=="Vacant":
            exit()
        elif ss==s:
            i+=max(N//count,1)
            count*=2
        else:
            i-=(N//count,1)
            count*=2        


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="Male":
    start=0
elif who=="Female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="Male":
        temp=0
    elif who=="Female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
total = 0


def gcd_list(*numbers):
    return reduce(math.gcd, numbers)


for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            s = [i, j, k]
            total += gcd_list(*s)

print(total)


### FIXED CODE ###

import math
from functools import reduce

K = int(input())
total = 0


def gcd_list(*numbers):
    return reduce(math.gcd, numbers)


for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            s = [i, j, k]
            if i == j == k:
                total += gcd_list(*s)
            elif i == j and j != k:
                total += gcd_list(*s) * 3
            elif i != j and j == k:
                total += gcd_list(*s) * 3
            else:
                total += gcd_list(*s) * 6

print(total)
### BUGGY CODE ###

import bisect
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    # print(a)
    # print(math.floor(a[-1] / 2))
    b = bisect.bisect_left(a, math.floor(a[-1] / 2))
    a.insert(b, math.floor(a[-1] / 2))
    a.pop(-1)

    if len(a) == 1:
        print(math.floor(a[0] / 2**(m - i - 1)))
        exit()
print(sum(a))


### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x * (-1), a))

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

c = list(map(lambda x: x * (-1), b))

print(sum(c))
### BUGGY CODE ###

l,r=map(int,input().split())
m=[i%2019 for i in range(l,r+1)]
print(0 if r-l>671 else min(i*j%2019 for i in m for j in m if i<j))

### FIXED CODE ###

mod = 2019
l, r = map(int, input().split())

if r//mod - l//mod > 0:
  print(0)
else:
  l %= mod
  r %= mod
  ans = mod - 1
  for i in range(l+1, r+1):
    for j in range(l, i):
      ans = min(i*j%mod, ans)
  print(ans)
### BUGGY CODE ###

n , k =list(map(int,input().split()))
p = list(map(int,input().split()))
maxval = 0
for i in range(n-k+1):
    if sum(p[i:i+k]) > maxval:
        maxval = sum(p[i:i+k])
        idx = i
print((maxval+k)/2)

### FIXED CODE ###

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

print((maxval+k)/2)
### BUGGY CODE ###

N, M = map(int, input().split())
A, W = [], []
num = 0

for i in range(M):
    P, S = map(str, input().split())
    if P not in A:
        if S == "AC":
            A.append(P)
        else:
            W.append(P)

for j in range(len(A)):
    num += W.count(A[j])

print(len(A), num)


### FIXED CODE ###

N, M = map(int, input().split())
ac = [0]*N
wa = 0

for i in range(M):
    P, S = map(str, input().split())
    P = int(P)-1
    if ac[P] != 1 and S == "AC":
        wa += abs(ac[P])
        ac[P] = 1
    elif ac[P] != 1 and S == "WA":
        ac[P] -= 1

print(ac.count(1), wa)
### BUGGY CODE ###

import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort(reverse=True)
ans = 0
P = []
for i in range(N-1):
    for j in range(i+1,N):
        P.append(L[i]+L[j])
now = 0
ans = 0
for i in range(N-2):
    now += N - (i + 1)
    A = P[now:]
    A.sort()
    index = bisect.bisect_left(A,L[i]+0.1)
    ans += (len(A) - index)
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort(reverse=True)
ans = 0
P = []
for i in range(N-1):
    for j in range(i+1,N):
        P.append(L[i]+L[j])
P.sort()
now = 0
ans = 0
for i in range(N-2):
    now += N - (i + 1)
    index = bisect.bisect_left(P,L[i]+0.1)
    ans += (len(P) - index)-now
print(ans)
### BUGGY CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_right(l[j+1:],l[i]+l[j]-1)
         
print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, P = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c + P))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    for k in e.keys():
      for t in e[k]:
        self.edges.append((k, t[0], t[1]))
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    for i in range(self.n + 1):
      for (u, v, c) in self.edges:
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
    return d[t]
  def path_findloop(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    first = 0
    for i in range(1, self.n * 2 + 1):
      for (u, v, c) in self.edges:
        if u != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i > N: d[v] = -float("inf")
      if i == self.n:
        first = d[t] + 0
      elif i == self.n * 2:
        if first != d[t]:
          return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path_findloop(1, N)
if res == "-loop": print(-1)
else: print(max(0, -res))

### FIXED CODE ###

import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))
### BUGGY CODE ###

R, C, K = map(int, input().split())
item = [[0] * C for i in range(R)]
for i in range(K):
  r, c, v = map(int, input().split())
  item[r - 1][c - 1] = v

dp = [[[0] * 4 for j in range(C)] for i in range(R)] 
#print(dp, item)


for i in range(R):
  for j in range(C):
    for k in range(4):
      if (i == 0) and (j == 0):
        continue
      else:
        if i == 0:
          dp[i][j][k] = dp[i][j - 1][k]
          #if (item[i][j] != 0) and (k != 0):
          #  dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + item[i][j])  
        elif j == 0:
          dp[i][j][k] = dp[i - 1][j][3]
          #if (item[i][j] != 0) and (k != 0):
          #  dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + item[i][j])           
        else:
          dp[i][j][k] = dp[i][j - 1][k]
          dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][3])
          #if (item[i][j] != 0) and (k != 0):
          #  dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + item[i][j])       
    #for k in range(3):
    #  dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
    
    for k in range(3):
          if (item[i][j] != 0):
            dp[i][j][3 - k] = max(dp[i][j][3 - k], dp[i][j][2 - k] + item[i][j])          

#print(item)            
#print(dp)
print(dp[-1][-1][-1])  



### FIXED CODE ###

R,C,K = map(int,input().split())
J=[0] * K
for i in range(K):
  J[i] = list(map(int,input().split()))

#DP0 = [[0]*(C+2) for i in range(R+2)]
DP1 = [[0]*(C+2) for i in range(R+2)]
DP2 = [[0]*(C+2) for i in range(R+2)]
DP3 = [[0]*(C+2) for i in range(R+2)]

MAP = [[0]*C for i in range(R)]

for x,y,v in J:
    MAP[x-1][y-1] = v
#print(MAP)
for i in range(R):
    for j in range(C):
        DP1[i][j] = max(DP1[i][j-1],DP1[i-1][j]+MAP[i][j],DP2[i-1][j]+MAP[i][j],DP3[i-1][j]+MAP[i][j])
        DP2[i][j] = max(DP2[i][j-1],DP1[i][j-1]+MAP[i][j])
        DP3[i][j] = max(DP3[i][j-1],DP2[i][j-1]+MAP[i][j])

#print(DP1)
#print(DP2)
#print(DP3)
ANS=0
for i in range(R):
    for j in range(C):
        ANS=max(ANS,DP1[i][j],DP2[i][j],DP3[i][j])
print(ANS)
### BUGGY CODE ###

def main():
    n = input()
    a = input().split(" ")
    res = [str(i+1) for i in range(len(a))]
    r = ""
    for i in res:
        r += str(a.index(i) + 1) + " "
    print(r[:-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    n = input()
    a = input().split(" ")
    # r = ""
    # for i in range(int(n)):
    #     r += str(a.index(str(i+1)) + 1) + " "
    # print(r[:-1])
    a = [(a[i],str(i+1)) for i in range(len(a))]
    a = list(map(lambda x:x[1],sorted(a,key=lambda x:int(x[0]))))
    print(" ".join(a))

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

import sys


def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    # H, W, M = 3, 3, 3
    # targets = ((1, 1), (2, 1), (1, 3))
    
    target_h = [0] * H
    target_w = [0] * W
    target_hw = set()
    for h, w in targets:
        target_h[h - 1] += 1
        target_w[w - 1] += 1
        target_hw.add((h - 1, w - 1))

    ans = 0
    for h, a in enumerate(target_h):
        if a:
            for w, b in enumerate(target_w):
                if b:
                    ans = max(ans, target_h[h] + target_w[w] - (1 if (h, w) in target_hw else 0))
    
    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import itertools


def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    
    target_h = {}
    target_w = {}
    target_hw = set()
    for h, w in targets:
        target_h[h] = target_h.setdefault(h, 0) + 1
        target_w[w] = target_w.setdefault(w, 0) + 1
        target_hw.add((h, w))

    max_h = max(target_h.values())
    max_w = max(target_w.values())

    h_set = {h for h, v in target_h.items() if max_h == v}
    w_set = {w for w, v in target_w.items() if max_w == v}

    ans = max_h + max_w - 1
    for hw in itertools.product(h_set, w_set):
        if hw not in target_hw:
            ans += 1
            break
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

H,W = map(int, input().split())
g = []
for _ in range(H):
    g.append(list(input()))

dp = [[10**9 for _ in range(W)] for __ in range(H)]

cnt = 0
#solve
def dfs(i, j, score, lc):
    if lc == '.' and g[i][j] == '#':
        score += 1
    dp[i][j] = min(dp[i][j], score)

    if i+1 < H:
        dfs(i+1, j, score, g[i][j])
    if j+1 < W:
        dfs(i, j+1, score, g[i][j])        

dfs(0, 0, 0, '.')
print(dp[H-1][W-1])

### FIXED CODE ###

H,W = map(int, input().split())
g = []
for _ in range(H):
    g.append(list(input()))

dp = [[10**9 for _ in range(W)] for __ in range(H)]

dp[0][0] = 1 if g[0][0] == '#' else 0
d = ([0,1], [1,0])
for ix in range(H):
    for jx in range(W):
        for dx,dy in d:
            ni = ix + dx
            nj = jx + dy
            if ni >= H or nj >= W:
                continue
            add = 0
            if g[ix][jx] == '.' and g[ni][nj] == '#':
                add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)


print(dp[H-1][W-1])
### BUGGY CODE ###

def main():
    s = input()
    sl = len(s)
    t = input()
    tl = len(t)

    dp = [[0] * (tl + 1) for _ in range(sl + 1)]

    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    answer = ''
    while sl > 0 and tl > 0:
        if s[sl - 1] == t[tl - 1]:
            sl -= 1
            tl -= 1
            answer += s[sl]
            continue

        if dp[sl - 1][tl] > dp[sl][tl - 1]:
            sl -= 1
        else:
            tl -= 1

    print(answer[::-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = [np.zeros(tl + 1, np.int32)]
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    np.maximum.accumulate(tmp, out=tmp)
    dp.append(tmp)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

s = []
for i in p:
  s.append((i*(i-1)/2+i)/i)

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

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

# 値ごとの期待値を取得
s = [0]*n
for i in range(n):
  s[i] = (p[i]+1)/2

# 期待値を累積していく
p = [0]*(n+1)
for i in range(1, n+1):
  p[i] = p[i-1] + s[i-1]

# 下記の方法で隣接する期待値合計を取得し、比較を行う。
# 隣接する期待値の合計　= 対象とする範囲の最大累積和　- 対象外範囲の最大累積和
ans = 0
for i in range(n-k+1):
  ans = max(ans, p[i+k] - p[i])

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

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]

dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            elif k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)

### FIXED CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]

dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            elif k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)
### BUGGY CODE ###

def resolve():
    def main():

        n=int(input())
        d=list(map(int,input().split()))
        m=int(input())
        t=list(map(int,input().split()))
        from collections import Counter
        dd=Counter(d)
        tt=Counter(t)
        ddkey=list(dd.keys())
        ddvalue=list(dd.values())
        for x,y in tt.items():
            flag=True
            if x in ddkey and ddvalue[ddkey.index(x)]>=y:
                continue
            else:
                return 'NO'
        return 'YES'
    print(main())
resolve()

### FIXED CODE ###

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

def resolve():
    def main():

        n=int(input())
        d=list(map(int,input().split()))
        m=int(input())
        t=list(map(int,input().split()))
        from collections import Counter
        dd=Counter(d)
        tt=Counter(t)
        for key,value in tt.items():
            if dd[key]<value:
                return 'NO'
        return 'YES'
    print(main())
resolve()
### BUGGY CODE ###

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

from collections import Counter
count = Counter(A)
 
s = 0
for c in list(count.values()):
    s += c*(c-1)/2

ans = 0
for a in A:
    n = A.count(a)
    ans = s - n*(n-1)/2 + (n-1)*(n-2)/2
    print(int(ans))

### FIXED CODE ###

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

from collections import Counter
count = Counter(A)
 
s = 0
for c in list(count.values()):
    s += c*(c-1)/2

ans = 0
for a in A:
    n = count[a]
    ans = s - n*(n-1)/2 + (n-1)*(n-2)/2
    print(int(ans))
### BUGGY CODE ###

S=int(input())
#294867501
maxlen=S//3
maxlist=[[0] * (S-2) for i in range(maxlen)]
suml=0
for i in range(1,maxlen+1):
  for j in range(3*i,S+1):
    if i==1:
      maxlist[i-1][j-3]=1
    else:
      maxlist[i-1][j-3]=(sum(maxlist[i-2][:j-6+1]))%(10**9+7)

for i in range(1,maxlen+1):
  suml+=maxlist[i-1][S-3]
suml=suml%(10**9+7)
  
print(suml)

### FIXED CODE ###

S=int(input())
#1729,294867501
maxlen=S//3
maxlist=[[0] * (S-2) for i in range(maxlen)]
suml=0
for i in range(1,maxlen+1):
  for j in range(3*i,S+1):
    if i==1 or j==3*i:
      maxlist[i-1][j-3]=1
    else:
      maxlist[i-1][j-3]=maxlist[i-1][j-4]+maxlist[i-2][j-6]

for i in range(1,maxlen+1):
  suml+=maxlist[i-1][S-3]
suml=suml%(10**9+7)
  
print(suml)
### BUGGY CODE ###

k,s=map(int,input().split())
print([x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)].count(s))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-z-y<=k]))
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
    if i<a+k or i>b-k:
        print(i)
        

### FIXED CODE ###

a,b,k=map(int,input().split())
p=set()
for i in range(min(k,b-a+1)):
    p.add(a+i)
    p.add(b-i)
k=sorted(list(p))
for i in range(len(k)):
    print(k[i])
### BUGGY CODE ###

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

sum = 0
for i,k in enumerate(L):
  for j in range(i+1, N):
    for l in range(j+1, N):
      if L[l] < L[j] + k:
        sum += 1
      else:
        break;
print(sum)

### FIXED CODE ###

import bisect
N = int(input())
L = [int(i) for i in input().split(' ')]
L.sort()

sum = 0
for i,k in enumerate(L):
  for j in range(i+1, N):
    sum += bisect.bisect_left(L,L[j] + k) - j - 1


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

n = int(input())
a = list(map(int, input().split()))
res = a[0]
for i in range(1, n): res *= a[i]
print(-1) if res > 10**18 else print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit()
a = sorted(a, reverse=True)
res = a[0]
for ai in a[1:]:
    res *= ai
    if res > 10**18:
        print(-1)
        exit()
print(res)
### BUGGY CODE ###

from collections import defaultdict
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    h = defaultdict(int)
    ans = 0
    for i in range(len(S)-1, -1, -1):
        s = int(S[i:])
        m = s % P
        if m == 0:
            h[m] += 1
            ans += h[m]
        else:
            ans += h[m]
            h[m] += 1

    print(ans)


### FIXED CODE ###

from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        m = s % P
        if m == 0:
            p[m] += 1
            ans += p[m]
        else:
            ans += p[m]
            p[m] += 1

    print(ans)