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

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*P >= g: return 1
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, done=[]):
    global m
    if m <= n: return
    elif point >= g: m = n
    elif flag(point,P[now],now):
        temp = math.ceil((g-point)/(100*(now+1)))
        n += temp
        if m > n: m = n
    else:
        done.append(now)
        if now == -1:
            for i in range(d):
                nxtdone = done[:]
                score(point, n, i, nxtdone)
        elif m <= n+P[now]: return
        else:
            for i in range(d):
                if not i in done:
                    nxtp = point+P[now]*100*(now+1) + C[now]
                    nxtn = n + P[now]
                    nxtdone = done[:]
                    score(nxtp, nxtn, i, nxtdone)

score()
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
xy = [LIST() for _ in range(N-1)]
tree = [[] for _ in range(N)]
for x, y in xy:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

def DFS(i, par, c):  # c:0->white, 1->black
    if par and len(tree[i]) == 1:
        return 1
    if c == 0:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= (DFS(node, i, 0) + DFS(node, i, 1))
                cnt %= mod
        return cnt
    elif c == 1:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= DFS(node, i, 0)
                cnt %= mod
        return cnt

ans = DFS(0, None, 0)+DFS(0, None, 1)
print(ans%mod)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
xy = [LIST() for _ in range(N-1)]
tree = [[] for _ in range(N)]
for x, y in xy:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

@lru_cache(maxsize=None)
def DFS(i, par, c):  # c:0->white, 1->black
    if par and len(tree[i]) == 1:
        return 1
    if c == 0:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= (DFS(node, i, 0) + DFS(node, i, 1))
                cnt %= mod
        return cnt
    elif c == 1:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= DFS(node, i, 0)
                cnt %= mod
        return cnt

ans = DFS(0, None, 0)+DFS(0, None, 1)
print(ans%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
while m>0:
  a[a.index(max(a))]=int(max(a)//2)
  m=m-1
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)
while m>0:
  heapq.heappush(a,(-1)*int((-1)*heapq.heappop(a)//2))
  m=m-1

print(-sum(a))
### BUGGY CODE ###

import copy
import bisect
N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        maxi = L[i] + L[j] -1
        #mini = abs(L[i] - L[j]) +1
        # mi = bisect.bisect_left(L[j+1:],mini)
        ma = bisect.bisect_right(L[j+1:], maxi)
        #print("mi"+str(mi)+"ma"+str(ma))
        if ma >= 0:
            count += ma
print(count)


### FIXED CODE ###


import bisect
N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        count += bisect.bisect(L,L[i]+L[j]-1)-j-1
print(count)
### BUGGY CODE ###

#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
#cdef int i,j,l,r,ll,rr
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
### BUGGY CODE ###

N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]
 
# initialize
best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2 + 1

# time complexity: O(N)?
for mid_sep in range(2, N - 1):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]
    for left_sep_cand in range(left_sep, mid_sep):
        # obtain the best first separation position
        if abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep_cand]) < abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]):
            left_sep = left_sep_cand
    for right_sep_cand in range(right_sep, N):
        # obtain the best third separation position
        if abs(cuml_A_list[-1] - cuml_A_list[right_sep_cand] - (cuml_A_list[right_sep_cand] - cuml_A_list[mid_sep]))\
            < abs(cuml_A_list[-1] - cuml_A_list[right_sep] - (cuml_A_list[right_sep] - cuml_A_list[mid_sep])):
            right_sep = right_sep_cand
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)


### FIXED CODE ###

N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]

best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2

# time complexity: O(N)
for mid_sep in range(1, N - 2):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]

    while abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]) > abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep + 1]):
        left_sep += 1
    while abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep] + cuml_A_list[mid_sep]) > abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep + 1] + cuml_A_list[mid_sep]):
        right_sep += 1
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)
### BUGGY CODE ###

from collections import defaultdict
ODD = defaultdict(int)
EVEN = defaultdict(int)
ALL = set([])
N = int(input())

A = list(map(int,input().split()))
for i in range(N):
  ALL.add(A[i])
  if i%2 == 0:
    EVEN[A[i]] += 1
  else:
    ODD[A[i]] += 1
if len(ALL) == 1:
  ans = N//2
  print(ans)
  exit()
modd = max(ODD.values())
meven = max(EVEN.values())
mlodd = [];mleven = []
dicodd = sorted(ODD.items(), key=lambda x:x[1], reverse = True)
diceven = sorted(EVEN.items(), key=lambda x:x[1], reverse = True)
ans = N
for x, vx in dicodd:
  for y, vy in diceven:
    if x != y:
      temp = N-(vx+vy)
      if ans != temp:
        ans = min(ans,temp)
      else:
        print(ans)
        exit()
print(ans)
exit()
print(ans)


### FIXED CODE ###

from collections import defaultdict
ODD = defaultdict(int)
EVEN = defaultdict(int)
ALL = set([])
N = int(input())

A = list(map(int,input().split()))
for i in range(N):
  ALL.add(A[i])
  if i%2 == 0:
    EVEN[A[i]] += 1
  else:
    ODD[A[i]] += 1
if len(ALL) == 1:
  ans = N//2
  print(ans)
  exit()
modd = max(ODD.values())
meven = max(EVEN.values())
mlodd = [];mleven = []
dicodd = sorted(ODD.items(), key=lambda x:x[1], reverse = True)
diceven = sorted(EVEN.items(), key=lambda x:x[1], reverse = True)
ans = N
if len(dicodd) > 1:
  X = [dicodd[0],dicodd[1]]
else:
  X = [dicodd[0]]
if len(diceven) > 1:
  Y = [diceven[0],diceven[1]]
else:
  Y = [diceven[0]]
#print(X)
#print(Y)
for x,v in X:
  for y,w in Y:
    if x == y:
      continue
    temp = N-(v+w)
    ans = min(ans,temp)

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

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[]
for i in range(H):
    grid.append(list(input()))

L=list2d(H, W, 0)
R=list2d(H, W, 0)
D=list2d(H, W, 0)
U=list2d(H, W, 0)

for i in range(H):
    cnt=0
    for j in range(W):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        L[i][j]=cnt
for i in range(H):
    cnt=0
    for j in range(W-1, -1, -1):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        R[i][j]=cnt
for i in range(W):
    cnt=0
    for j in range(H):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        D[j][i]=cnt
for i in range(W):
    cnt=0
    for j in range(H-1, -1, -1):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        U[j][i]=cnt

ans=0
for i in range(H):
    for j in range(W):
        if grid[i][j]!='#':
            ans=max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[]
for i in range(H):
    grid.append(list(input()))

L=list2d(H, W, 0)
R=list2d(H, W, 0)
D=list2d(H, W, 0)
U=list2d(H, W, 0)

for i in range(H):
    cnt=0
    for j in range(W):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        L[i][j]=cnt
for i in range(H):
    cnt=0
    for j in range(W-1, -1, -1):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        R[i][j]=cnt
for i in range(W):
    cnt=0
    for j in range(H):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        D[j][i]=cnt
for i in range(W):
    cnt=0
    for j in range(H-1, -1, -1):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        U[j][i]=cnt

ans=0
for i in range(H):
    for j in range(W):
        if grid[i][j]!='#':
            ans=max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)
### BUGGY CODE ###

n,k,q = map(int, input().split())
al = [int(input()) for i in range(q)]
for i in range(n):
    print('Yes' if k-(q-al.count(i+1))>0 else 'No')

### FIXED CODE ###

n,k,q = map(int, input().split())
ans = [0]*n
for i in range(q):
    w = int(input())
    ans[w-1]+=1
for i in range(n):
        print('Yes' if ans[i]>=q-k+1 else 'No')
### BUGGY CODE ###

import itertools
R,G,B,N = map(int, input().split())
count = 0
Rc = [i * R for i in range(0, int(N / R) +1)]
Gc = [i * G for i in range(0, int(N / G) +1)]
Bc = [i * B for i in range(0, int(N / B) +1)]
#print(Rc)
#print(Gc)
#print(Bc)
Combi = list(itertools.product(Rc, Gc, Bc))
print(sum([True for i in Combi if sum(i) == N]))

### FIXED CODE ###

R,G,B,N = map(int, input().split())
count = 0
for r in range(N // R + 1) :
    for g in range((N - r*R) // G + 1) :
        if (N - r*R - g*G) %B == 0 :
            count += 1
print(count)
### BUGGY CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, M = [int(x) for x in input().split()]
    HW = [[int(x) for x in input().split()] for _ in range(M)]

    x = set()

    hc = collections.Counter()
    wc = collections.Counter()

    for h, w in HW:
        hc[h] += 1
        wc[w] += 1
        x.add((h, w))

    ans = 0
    hcma = hc.most_common()[0][1]
    wcma = wc.most_common()[0][1]
    f = False
    for a in hc.most_common():
        if a[1] != hcma:
            break
        for b in wc.most_common():
            if b[1] != wcma:
                break
            if (a[0], b[0]) in x:
                ans = max(ans, hcma + wcma - 1)
            else:
                ans = max(ans, hcma + wcma)
                f = True
                break
        if f:
            break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, M = [int(x) for x in input().split()]
    HW = [[int(x) for x in input().split()] for _ in range(M)]

    x = set()

    hc = collections.Counter()
    wc = collections.Counter()

    for h, w in HW:
        hc[h] += 1
        wc[w] += 1
        x.add((h, w))

    ans = 0
    hcma = hc.most_common()[0][1]
    wcma = wc.most_common()[0][1]
    f = False
    bost_common = wc.most_common()
    for a in hc.most_common():
        if a[1] != hcma:
            break
        for b in bost_common:
            if b[1] != wcma:
                break
            if (a[0], b[0]) in x:
                ans = max(ans, hcma + wcma - 1)
            else:
                ans = max(ans, hcma + wcma)
                f = True
                break
        if f:
            break

    print(ans)


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

import sys

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

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                break
        t += 1

main()


### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
### BUGGY CODE ###

def gcd(m, n):
    return m if n == 0 else gcd(n, m%n)


def lcm(m, n):
    return m // gcd(m, n) * n


def main():
    MOD = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    m = 1
    for i in a:
        m = lcm(m, i)
    
    ans = 0
    for i in a:
        b = m // i
        ans += b
        ans %= MOD
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def gcd(m, n):
    return m if n == 0 else gcd(n, m%n)


def lcm(m, n):
    return m // gcd(m, n) * n


def main():
    MOD = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    m = 1
    for i in a:
        m = lcm(m, i)
    
    ans = 0
    for i in a:
        b = m // i
        ans += b
    
    print(ans%MOD)


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

n=int(input())
def f(n):
    lower_divisors = []
    upper_divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
    upper_divisors.reverse()
    return n*len(lower_divisors + upper_divisors)
sumi=0
for i in range(1,n+1):
    sumi+=f(i)
print(sumi)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
  y=n//i
  ans+=y*(y+1)*i//2
print(ans)
### BUGGY CODE ###

K, N = map(int, input().split())
arr = list(map(int, input().split()))
dist = [K-arr[N-1]+arr[0]]
for i in range(1,N):
    dist.append(arr[i]-arr[i-1])
ans = sum(dist)
for i in range(N):
    ans = min(ans,sum(dist)-dist[i])
print(ans)

### FIXED CODE ###

K, N = map(int, input().split())
arr = list(map(int, input().split()))
dist = [K-arr[N-1]+arr[0]]
for i in range(1,N):
    dist.append(arr[i]-arr[i-1])
tmp = sum(dist)
ans = sum(dist)
for i in range(N):
    ans = min(ans,tmp-dist[i])
print(ans)
### BUGGY CODE ###

import math
import numpy as np

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

dic = {} #ここに結果を保存していく。

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2:
        dic[t] = 1
    else:
        temp = math.floor(k/t)**n
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp
ans = 0
moddo = 10**9+7
for i in range(1,k+1):
    ans += i*dic[i]
    if ans >= moddo:
        ans = ans%moddo
    
        
#print(dic)
#print(sum(dic.values()))
print(ans)

### FIXED CODE ###

import math

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

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

S = input()
N = int(input())
ls = [[i for i in input().split()] for j in range(N)]

for l in ls:
    if l[0]=="1": # 反転
        S = S[::-1]
    elif l[0]=="2":
        if l[1] == "1":
            S = l[2] + S
        elif l[1] == "2":
            S = S + l[2]

print(S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
Flag = True
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        Flag = False if Flag else True
    else:
        if Flag:
            if q[1] == '1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1] == '1':
                S.append(q[2])
            else:
                S.appendleft(q[2])
if Flag:
    print(''.join(S))
else:
    print(''.join(reversed(S)))
### BUGGY CODE ###

S = str(input())
Q = int(input())

#Que = [list(map(str, input().split())) for _ in range(Q)]


re_flag = 1
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        re_flag *= -1

    else:
        if que[2] == '1':
            if re_flag == 1:
                S = que[4:] + S
            else:
                S =  S + que[-1:3:-1]
        if que[2] == '2':
            if re_flag == 1:
                S = S + que[4:]
            else:
                S = que[-1:3:-1] + S

if re_flag == -1:
    S = S[::-1]

print(S)

### FIXED CODE ###

from  collections import deque

S = str(input())
Q = int(input())

#Que = [list(map(str, input().split())) for _ in range(Q)]

deque_S = deque(S)
re_flag = 1
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        re_flag *= -1

    else:
        if que[2] == '1':
            if re_flag == 1:
                #S = que[4:] + S
                deque_S.appendleft(que[4:])
            else:
                #S =  S + que[-1:3:-1]
                deque_S.append(que[-1:3:-1])
        if que[2] == '2':
            if re_flag == 1:
                #S = S + que[4:]
                deque_S.append(que[4:])
            else:
                #S = que[-1:3:-1] + S
                deque_S.appendleft(que[-1:3:-1])

ans = ''
if re_flag == 1:
    ans = ''.join(deque_S)
else:
    ans = ''.join(deque_S)[::-1]
#print(deque_S)

print(ans)