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

import re

S = str(input())
k=int(0)

for i in range(20000):
#while S.find('ABC')>=0:
#    S = S[:S.rfind('ABC')] + 'BCA' + S[(S.rfind('ABC')+3):]
#    k +=1
    matchedList = re.findall("ABC",S)
    k += len(matchedList)
    S = S.replace('ABC', 'BCA')

ans = (int(k))

print(ans)

### FIXED CODE ###

s = input()
ans = 0
cntA = 0
for i in range(0, len(s) - 1):
    if s[i] == 'A':
        cntA += 1
    elif s[i: i + 2] == "BC":
        ans += cntA
    elif i > 0 and s[i - 1: i + 1] == "BC":
        continue
    else:
        cntA = 0
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = 1
flag = False
for i in a:
    ans *= i
    if (ans > pow(10,18)):
        flag = True

if (flag):
    ans = -1
if 0 in a:
    ans = 0

print(ans)




### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = 1
flag = False
zeros = False
over = pow(10,18)
for i in a:
    if flag == False:
        ans *= i
    if (ans > over):
        flag = True
    if i == 0:
        zeros = True

if (flag):
    ans = -1
if (zeros):
    ans = 0

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

import math
def com(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

from collections import Counter,defaultdict
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
#print(cnt)

ans=defaultdict(lambda :0)
for i in set(a):
    temp=cnt[i]-1
    for x,y in cnt.items():
        if x!=i and y>=2:
            ans[i]+=(y-1)*y//2
        elif x==i and temp>=2:
            ans[i]+=(temp-1)*temp//2

for i in a:
    print(ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
#print(cnt)

ans=0
for i in cnt.values():
    ans=ans+i*(i-1)//2

for i in a:
    print(ans-cnt[i]+1)
### BUGGY CODE ###

import numpy as np

def draft(A, K, N):
    A = np.array(A)
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

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

import numpy as np
import math

def Split(cum_):
    S_ = cum_[-1]
    idx_ = np.argmin(np.abs(S_ - 2 * cum_))
    cum1_ = cum_[:idx_ + 1]
    cum2_ = cum_[idx_ + 1:] - cum_[idx_]
    return cum1_[-1], cum2_[-1]


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = np.cumsum(A)

res = 10 ** 15
for ib in range(N-3):
    for ic in range(ib+1, N-2):
        P = CumA[ib]
        Q = CumA[ic] - P
        R, S = Split(CumA[ic+1:] - CumA[ic])
        res = min(res, max([P, Q, R, S]) - min([P, Q, R, S]))

print(res)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


def left_diff(array):
    """
    array: ordered ndarray, len(array) >= 2
    """
    x = (array[-1] + 1) >> 1
    mid = np.searchsorted(array, x)
    if abs(array[-1] - array[mid] * 2) < abs(array[-1] - array[mid-1] * 2):
        return array[mid], array[-1] - array[mid]
    else:
        return array[mid-1], array[-1] - array[mid-1]


def right_diff(array, offset):
    """
    array: ordered ndarray, len(array) >= 2
        target array or list

    offset: int
        offset value for right array
    """
    x = (array[-1] - offset + 1) >> 1
    mid = np.searchsorted(array, x + offset)
    if abs(array[-1] - array[mid] * 2 + offset)\
            < abs(array[-1] - array[mid-1] * 2 + offset):
        return array[mid] - offset, array[-1] - array[mid]
    else:
        return array[mid-1] - offset, array[-1] - array[mid-1]


def calc_max_diff(p, q, r, s):
    return max(p, q, r, s) - min(p, q, r, s)


if __name__ == '__main__':
    N = d_in()
    a_array = np.array(ds_in())

    cum_a = np.cumsum(a_array)
    left_cut_points = (cum_a[1:-2] + 1) // 2
    left_mid_points = np.searchsorted(cum_a, left_cut_points)
    right_cut_points = (cum_a[-1] + cum_a[1:-2] + 1) // 2
    right_mid_points = np.searchsorted(cum_a, right_cut_points)
    
    ans = float('inf')
    for i in range(2):
        for j in range(2):
            P = cum_a[left_mid_points-i]
            Q = cum_a[1:-2] - P
            R = cum_a[right_mid_points-j] - cum_a[1:-2]
            S = cum_a[-1] - cum_a[right_mid_points-j]
            MAX = np.maximum(np.maximum(P, Q), np.maximum(R, S))
            MIN = np.minimum(np.minimum(P, Q), np.minimum(R, S))
            ans = min(ans, (MAX - MIN).min())

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

import math
a, b, n = map(int, input().split())

ans = [math.floor(a*i/b)-a*math.floor(i/b) for i in range(n+1)]
print(max(ans))

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
if b>n:
    print(math.floor(a*n/b))
else:
    x = b-1
    print(math.floor(a*x/b))
### BUGGY CODE ###

n = int(input())

cnt = 0
k = []
for i in range(1, n + 1):
    x = 1
    while x ** 2 < n:
        y = 1
        s_x = x ** 2
        while y ** 2 < n:
            z = 1
            s_y = y ** 2
            while z ** 2 < n:
                if s_x + s_y + z ** 2 + x * y + y * z + z * x == i:
                    cnt += 1

                z += 1
            y += 1
        x += 1
    print(cnt)
    cnt = 0
# print(k)


### FIXED CODE ###

n = int(input())
ans = [0] * n
cnt = 0
k = []
x = 1
while x ** 2 < n:
    y = 1
    s_x = x ** 2
    while y ** 2 < n:
        z = 1
        s_y = y ** 2
        while z ** 2 < n:
            ans_tmp = s_x + s_y + z ** 2 + x * y + y * z + z * x
            if ans_tmp <= n:
                ans[ans_tmp - 1] += 1
            cnt += 1
            z += 1
        y += 1
    x += 1

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

for i in range(n):
    ans = li.count(i+1)
    print(ans)

### FIXED CODE ###

n = int(input())
list = list(map(int, input().split()))
data = [0] * n

for i in list:
    i -= 1
    data[i] += 1

for j in data:
    print(j)
### BUGGY CODE ###

k,s=map(int,input().split())

count=0
for x in range (k+1):
  for y in range (k+1):
    for z in range(k+1):
      if x+y+z==s:
        count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0
for a in range(k+1):
  for b in range(k+1):
    if 0<=s-a-b<=k:
      count+=1
print(count)
### BUGGY CODE ###

from functools import reduce

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    ans = reduce(lambda x,y:int(x)*int(y), A)

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


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
keta=[0]*60
for i in range(n):
    for j in range(60):
        if (a[i]>>j)&1==1:
            keta[j]+=1

s=sum(a)
ans=0
for i in range(n):
    s-=a[i]
    j=0
    tmp2=a[i]
    while tmp2!=0:
        if tmp2%2==1:
            keta[j]-=1
            ans+=(2**j)*((n-(i+1)-keta[j]*2))
        j+=1
        tmp2=tmp2//2
    ans+=s
    ans%=mod
    # print(ans,s)
    # print(keta)
print(ans%mod)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
keta=[0]*60
lis=[]
for i in range(n):
    tmp=[]
    for j in range(60):
        if (a[i]>>j)&1==1:
            keta[j]+=1
            tmp.append(j)
    lis.append(tmp)

s=sum(a)
ans=0
for i in range(n):
    s-=a[i]
    j=0

    for j in range(len(lis[i])):
        tmp2=lis[i][j]
        keta[tmp2]-=1
        ans+=(2**tmp2)*((n-(i+1)-keta[tmp2]*2))
    ans+=s
    ans%=mod
print(ans%mod)
### BUGGY CODE ###

# D - Lamp

H, W = map(int, input().split())
M = [[str(m) for m in input()] for _ in range(H)]
U = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j] != '#':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

        k, l = H - i - 1, W - j - 1
        if M[k][l] != '#':
            if i == 0:
                D[k][l] = 1
            else:
                D[k][l] = D[k + 1][l] + 1
            if j == 0:
                R[k][l] = 1
            else:
                R[k][l] = R[k][l + 1] + 1

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

print(ans)


### FIXED CODE ###

# # D - Lamp

import numpy as np

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
M = (np.array(M) == '.') * 1

L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)

for i in range(W):
    if i == 0:
        L[:, i] = M[:, i]
        R[:, W - i - 1] = M[:, W - i - 1]
    else:
        L[:, i] = (L[:, i - 1] + 1) * M[:, i]
        R[:, W - i - 1] = (R[:, W - i] + 1) * M[:, W - i - 1]

for i in range(H):
    if i == 0:
        U[i, :] = M[i, :]
        D[H - i - 1, :] = M[H - i - 1, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * M[i, :]
        D[H - i - 1, :] = (D[H - i, :] + 1) * M[H - i - 1, :]

print(max(np.max(L + R + D + U - 3), 0))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)
### BUGGY CODE ###

n = int(input())
ss =[]
num = 0

for i in range(n):
    s = input()
    if s not in ss:
        ss.append(s)
        num += 1

print(num)


### FIXED CODE ###

n = int(input())
ss = {}
num = 0

for i in range(n):
    s = input()
    if s not in ss:
        ss[s] = "exist"
        num += 1

print(num)
### BUGGY CODE ###

a = list(map(int,input().split()))
results = [int(input()) for i in range(a[2])]

points = [a[1]] * a[0]

for result in results:
    points = list(map(lambda x: x - 1, points))
    points[result - 1] = points[result - 1] + 1


for point in points:
    if point > 0:
        print('Yes')
    else:
        print('No')
    

### FIXED CODE ###

a = list(map(int,input().split()))
results = [int(input()) for i in range(a[2])]

points = [a[1]] * a[0]
points = list(map(lambda x: x - a[2], points))

for result in results:
    points[result - 1] = points[result - 1] + 1


for point in points:
    if point > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]

a.sort()
f.sort(reverse=True)

af = [[0 for i in range(3)] for j in range(n)]

for i in range(n):
    af[i][0] = a[i]*f[i]
    af[i][1] = a[i]
    af[i][2] = f[i]
    
af.sort(reverse=True)

if k == 0:
    print(af[0][0])
    exit()

low = -1
high = af[0][0]+1
tmp = 0

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    #print(mid)
    
    for i in range(n):
        tmp += max(0,af[i][1] - mid // af[i][2])
    #print(tmp)
    
    if tmp <= k:
        high = mid
    else:
        low = mid
        
if tmp > k:
    print(mid+1)
else:
    print(mid)


### FIXED CODE ###

import bisect

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]

a.sort()
f.sort(reverse=True)

af = [[0 for i in range(3)] for j in range(n)]

for i in range(n):
    af[i][0] = a[i]*f[i]
    af[i][1] = a[i]
    af[i][2] = f[i]
    
af.sort(reverse=True)

if k == 0:
    print(af[0][0])
    exit()

low = -1
high = af[0][0]+1
tmp = 0

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    #print(mid)
    
    for i in range(n):
        tmp += max(0,af[i][1] - mid // af[i][2])
    #print(tmp)
    
    if tmp <= k:
        high = mid
    else:
        low = mid
        
if tmp > k:
    print(mid+1)
else:
    print(mid)
### BUGGY CODE ###

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

# bfs 
C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.':
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list
black = 0
for h in C:
    for v in h:
        if v == "#":
            black += 1
print(H*W-black-count-1)

### FIXED CODE ###

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

# bfs 
C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.' and len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list

if C[H-1][W-1] == '.':
    print(-1)
else:
    black = 0
    for h in C:
        for v in h:
            if v == "#":
                black += 1
    print(H*W-black-count-1)
### BUGGY CODE ###

H, W = [int(i) for i in input().split(" ")]
S = []
for i in range(H):
  S.append(input())

def calc_len(S,r,c):
  count = 1
  
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
    count = calc_len(S,r,c)
    ans = max(count, ans) 

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

n = int(input())
l = [None] * n
ans = 0
for i in range(n):
    l[i] = sorted(input())
for i in range(n-1):
    for j in range(i+1, n):
        if l[i] == l[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in d:
        ans += d[s]
        d[s] += 1
    else:
        d[s] = 1
print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(gcd(i,j),k)
print(ans)
exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0
d = {}
vals = []
for i in range(1, K+1):
    for j in range(1, K+1):
        nums = [i,j]
        nums.sort()
        key = str(i) + '-' + str(j)
        if key in d:
            vals.append(d[key])
        else:
            val = gcd(i,j)
            d[key] = val
            vals.append(val)
#  print(vals)
#  print(d)
for val in vals:
    for k in range(1, K+1):
        #  print(val, k)
        nums = [i,j]
        nums.sort()
        key = str(val) + '-' + str(k)
        if key in d:
            ans += d[key]
        else:
            val = gcd(val, k)
            ans += val
            d[key] = val
print(ans)
exit()
### BUGGY CODE ###

#n段の上り方のバリエーションはフィボナッチ数列になっている

N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if i in alist:
        li[i] = 0
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))

### FIXED CODE ###

N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if len(alist)>=1 and i ==  alist[0]:
        li[i] = 0
        alist.pop(0)
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))
### BUGGY CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
for i in a:
    s_a = [x for x in sorted(a) if x[0] == i[0]]
    print(str(i[0]).zfill(6) + str(s_a.index(i)+1).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
p = [list(map(int, input().split())) + [i] for i in range(M)]
p.sort()
i = 0
for n in range(1, N + 1):
    count = 1
    while not(i >= M or p[i][0] != n):
        p[i] += [str(n).zfill(6) + str(count).zfill(6)]
        i += 1
        count += 1
p.sort(key=lambda x: x[2])
for a in p:
    print(a[3])
### BUGGY CODE ###

ab=[]
h,n=map(int,input().split())
dp=[10**9]*(h+10001)
dp[0]=0
for i in range(n):
	x,y=map(int,input().split())
	ab.append([x,y])
for i in range(1,h+10001):
	for j in range(n):
		if i>=ab[j][0]:
			dp[i]=min(dp[i],dp[i-ab[j][0]]+ab[j][1])
ans=min(dp[h:])
print(ans)

### FIXED CODE ###

h,n=map(int,input().split())
ab=[]
p=0
for i in range(n):
	a,b=map(int,input().split())
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)