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

import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
heapq._heapify_max(a)

okaiage = []
heapq._heapify_max(okaiage)
_heappush_max(okaiage, _heappop_max(a)/2)

m = M - 1
for j in range(N-1):
    temp_oka = _heappop_max(okaiage)
    temp_a = _heappop_max(a)
    #print(temp_oka, temp_a)
    if m > 0:
        if temp_a > temp_oka:
            _heappush_max(okaiage, temp_a/2)
            _heappush_max(okaiage, temp_oka)
        else:
            _heappush_max(okaiage, temp_a)
            _heappush_max(okaiage, temp_oka/2)
    else:
        _heappush_max(okaiage, temp_a)
        _heappush_max(okaiage, temp_oka)
    m -= 1
if m > 0:
    for i in range(m):
        temp_oka = _heappop_max(okaiage) / 2
        _heappush_max(okaiage, temp_oka)
#print(okaiage)
okaiage_kiri = [int(math.floor(_heappop_max(okaiage))) for i in range(N)]
#print(okaiage_kiri)
print(sum(okaiage_kiri))


### FIXED CODE ###

import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
heapq._heapify_max(a)

for j in range(M):
    _heappush_max(a, _heappop_max(a)//2)
print(sum(a))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
agm = uf.all_group_members()
ufr = uf.roots()
ans = 0
for i in ufr:
    ans = max(ans,len(agm[i]))
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
ufr = uf.roots()
ans = 0
for i in ufr:
    ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

import sys
 
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic = {i:sys.maxsize for i in range(2 ** n)}
dic[0] = 0
 
for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    dic2[k|c] = min(dic2[k|c],a+v)
    
  dic = dic2
 
if dic[(2**n)-1] != sys.maxsize:
  print(dic[(2**n) -1])
else:
  print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
 
dic = {0:0}
 
for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic2.keys():
      dic2[k|c] = min(dic2[k|c],a+v)
    else:
      dic2[k|c] = a+v
 
  dic = dic2
 
if ((2**n)-1) in dic.keys():
  print(dic[(2**n) -1])
else:
  print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
	n=int(input())
	A=list(map(int,input().split()))
	res=0

	for i in range(n):
		for j in range(i+1,n):
			if abs(i-j)==A[i]+A[j]:
				res+=1
	print(res)
	
if __name__ == '__main__':
	main()

### FIXED CODE ###

from collections import defaultdict

n=int(input())
A=list(map(int,input().split()))
B=defaultdict(int)
res=0

for i in range(n):
	B[A[i]+i]+=1
	if i-A[i] in B:
		res+=B[i-A[i]]

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

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh*(W+4)+sw] = 0
d.append(sh*(W+4)+sw)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.append(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list()
b = list()
for i in range(n):
    x = input()
    a.append(int(x))
b = sorted(a)
for i in range(n):
    if b[-1] == a[i] and a.count(b[-1]):
        print(b[-2])
    else:
        print(b[-1])

### FIXED CODE ###

n = int(input())
a = list()
for i in range(n):
    x = input()
    a.append(int(x))
second = sorted(a)[-2]
m = max(a)
for i in range(n):
    if m == a[i]:
        print(second)
    else:
        print(m)
### BUGGY CODE ###

def bisect(s,t):
    ok,ng=len(s),-1
    while ok-ng>1:
        mid=(ok+ng)//2
        if s[mid]>t:ok=mid
        else:ng=mid
    return ok


inf=10**12

a,b,q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(a)]+[inf];s.sort()
t=[-inf]+[int(input()) for _ in range(b)]+[inf];t.sort()

for i in range(q):
    x=int(input())
    p=bisect(s,x)
    q=bisect(t,x)

    sl,sr,tl,tr=s[p-1],s[p],t[q-1],t[q]

    sltl=x-min(sl,tl)
    srtr=max(sr,tr)-x
    sltr=min(x-sl*2+tr,-x-sl+tr*2)
    srtl=min(x-tl*2+sr,-x-tl+sr*2)
    print(min(sltl,srtr,sltr,srtl))

### FIXED CODE ###

import math
import bisect
inf=10**12
a,b,q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(a)]+[inf];s.sort()
t=[-inf]+[int(input()) for _ in range(b)]+[inf];t.sort()

for i in range(q):
    x=int(input())
    p=bisect.bisect_left(s,x)
    q=bisect.bisect_left(t,x)

    sl,sr,tl,tr=s[p-1],s[p],t[q-1],t[q]

    sltl=x-min(sl,tl)
    srtr=max(sr,tr)-x
    sltr=min(x-sl*2+tr,-x-sl+tr*2)
    srtl=min(x-tl*2+sr,-x-tl+sr*2)
    print(min(sltl,srtr,sltr,srtl))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lr_list = list()
for _ in range(m):
    lr_list.append(list(map(int, input().split())))

card_list = [i for i in range(1, n + 1)]

for l, r in lr_list:
    new_card_list = []
    for card in card_list:
        if card >= l and card <= r:
            new_card_list.append(card)
    card_list = new_card_list

print(len(card_list))

### FIXED CODE ###

n, m = list(map(int, input().split()))
# lr_list = list()
l_list = list()
r_list = list()
for _ in range(m):
    l, r = list(map(int, input().split()))
    l_list.append(l)
    r_list.append(r)
    # lr_list.append(list(map(int, input().split())))

min_r = min(r_list)
max_l = max(l_list)
if max_l <= min_r:
    print(min_r - max_l + 1)
else:
    print(0)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

print(now_d)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

print(now_d)
### BUGGY CODE ###

from collections import deque
S = input()
ans = deque(S)
Q = int(input())
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        ans.reverse()
    elif a_list[1] == "1":
        ans.appendleft(a_list[2])
    else:
        ans.append(a_list[2])
print(*ans, sep = "")

### FIXED CODE ###

from collections import deque
S = input()
ans = deque(S)
Q = int(input())
rev = False
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        if rev == True:
            rev = False
        else:
            rev = True
    elif (a_list[1] == "1" and rev == False) or (a_list[1] == "2" and rev == True):
        ans.appendleft(a_list[2])
    else:
        ans.append(a_list[2])
if rev:
    ans.reverse()
ans = "".join(ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
	n=int(input())
	A=list(map(int,input().split()))
	res=0

	for i in range(n):
		for j in range(i+A[i]+1,n):
			if abs(i-j)==A[i]+A[j]:
				res+=1
	print(res)
	
if __name__ == '__main__':
	main()


### FIXED CODE ###

from collections import defaultdict

n=int(input())
A=list(map(int,input().split()))
B=defaultdict(int)
res=0

for i in range(n):
	B[A[i]+i]+=1
	if i-A[i] in B:
		res+=B[i-A[i]]

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

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def cal(h, w, a):
    q = deque()
    counts = [[False for _ in range(w)] for _ in range(h)]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j][i] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if not counts[y0][x0]:
                    counts[y0][x0] = True
                    q.append([x0, y0, z+1])
    return z

print(cal(h, w, a))


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline

    n = input().rstrip()
    a_list = [int(x) for x in input().rstrip().split(" ")]

    import itertools

    c = itertools.combinations(a_list, 2)

    x = 1000000007

    ans = sum([v[0] * v[1] for v in c]) % x

    print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline

    n = input().rstrip()
    past_a = 0

    ans = 0
    for a in input().rstrip().split(" "):
        a = int(a)
        ans += a * past_a
        past_a += a

    x = 1000000007

    ans = ans % x

    print(ans)

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

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

ans = 0
for i in range(0, N):
    for j in range(0, i+1):
        if P[i] > P[j]:
            break

        if i == j:
            ans += 1

print (ans)



### FIXED CODE ###

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

ans = 0
min_v = P[0]

for i in range(0, N):
    if P[i] <= min_v:
        ans += 1
        min_v = P[i]

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

import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[-1 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
# dp = [[[0 for _ in range(3+1)] for _ in range(C+1)] for _ in range(R+1)]
dp = [[[0 for _ in range(R+1)] for _ in range(C+1)] for _ in range(3+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        for i in range(4):
            # 取らない
            if r < R:
                # dp[r+1][c][0] = max(dp[r][c][i], dp[r+1][c][0])
                dp[0][c][r+1] = max(dp[i][c][r], dp[0][c][r+1])
            if c < C:
                # dp[r][c+1][i] = max(dp[r][c][i], dp[r][c+1][i])
                dp[i][c+1][r] = max(dp[i][c][r], dp[i][c+1][r])

            # 取る
            if i < 3:
                # print(r, c, i)
                # dp[r+1][c][0] = max(dp[r][c][i] + grid[r][c], dp[r+1][c][0])
                # dp[r][c+1][i+1] = max(dp[r][c][i] + grid[r][c], dp[r][c+1][i+1])
                dp[0][c][r+1] = max(dp[i][c][r] + grid[r][c], dp[0][c][r+1])
                dp[i+1][c+1][r] = max(dp[i][c][r] + grid[r][c], dp[i+1][c+1][r])

# print(dp[R][C])
# print(max(dp[R-1][C]))
print(max((dp[0][C][R-1], dp[1][C][R-1], dp[2][C][R-1], dp[3][C][R-1])))

### FIXED CODE ###

import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
dp0 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for _ in range(R+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        # 取らない
        dp0[r+1][c] = max((dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c]))
        dp1[r][c+1] = max(dp1[r][c], dp1[r][c])
        dp2[r][c+1] = max(dp2[r][c], dp2[r][c])
        dp3[r][c+1] = max(dp3[r][c], dp3[r][c])

        if grid[r][c] == 0:
            continue
        # 取る
        dp0[r+1][c] = max(dp0[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp1[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp2[r][c] + grid[r][c], dp0[r+1][c])

        dp1[r][c+1] = max(dp0[r][c] + grid[r][c], dp1[r][c+1])
        dp2[r][c+1] = max(dp1[r][c] + grid[r][c], dp2[r][c+1])
        dp3[r][c+1] = max(dp2[r][c] + grid[r][c], dp3[r][c+1])

# print(dp0)
# print(dp1)
# print(dp2)
# print(dp3)
# print(max((dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C])))
print(dp0[R][C-1])
### BUGGY CODE ###

n,k=map(int,input().split())
MOD=10**9+7
ans=0
baig=[0]*(10**5+1)

for i in range(1,k+1):
    baig[i]=(k//i)**n%MOD

for j in range(k,0,-1):
    for jj in range(2*j,k+1,j):
        baig[j]-=baig[jj]
    baig[j]%=MOD
    ans+=baig[j]*j
    ans%=MOD

print(int(ans))



### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = pow(k // i , n , MOD)

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007

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

childs = [0] * N
seen = [False] * N
prev = [-1] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            prev[nv] = v
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

pow2 = pow(2, N - 1, MOD)


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    if prev[v] != -1:
        nodes.append(N - childs[v] - 1)
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2 - (sum(pow(2, n, MOD) - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = pow(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count)
    ans += dic[x % MOD]
    dic[x % MOD] += 1
    count += 1

print (ans)


### FIXED CODE ###

from collections import defaultdict

S = list(input())
N = len(S)

dic = defaultdict(int)
dic[0] = 1

ans = 0

tmp = 0
for i in range(N):
    s = S[N - 1 - i]
    tmp += int(s) * pow(10, i, 2019)
    ans += dic[tmp % 2019]
    dic[tmp % 2019] += 1

print (ans)

# print (dic)
### BUGGY CODE ###

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

t_voted, a_voted = ratio[0][0], ratio[0][1]
for t, a in ratio[1:]:
    tt, aa = t, a
    while tt < t_voted or aa < a_voted:
        tt += t
        aa += a
    t_voted, a_voted = tt, aa

print(t_voted + a_voted)


### FIXED CODE ###

from decimal import Decimal
from math import ceil

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

t_voted = a_voted = 1
for t, a in ratio:
    val = max(ceil(Decimal(t_voted) / Decimal(t)), ceil(Decimal(a_voted) / Decimal(a)))
    t_voted = t * val
    a_voted = a * val

print(t_voted + a_voted)