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

import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
TF = [False for _ in range(N)]
kouho = []
ans = 0

# 後ろから見て優先度付きキューで取り出す
mae = 0
for i in reversed(range(M)):
    mae += 1
    for n in range(N):
        if AB[n][0] <= mae and TF[n] != True:
            kouho.append([n, AB[n][0], AB[n][1]])
    kouho = sorted(kouho, key=lambda x: x[2], reverse=True)
    if len(kouho) != 0:
        n, A, B = kouho[0]
        TF[n] = True
        ans += B
        kouho = []
    
print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
kouho = []
ans = 0

AB = sorted(AB)

# 後ろから見て優先度付きキューで取り出す
n = 0
heapq.heapify(kouho)
for i in range(1, M+1):
    if n < N:
        while AB[n][0] <= i:
            heapq.heappush(kouho, AB[n][1] * (-1))
            n += 1
            if n >= N:
                break
    
    if kouho:
        b = heapq.heappop(kouho)
        ans += b*(-1)
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def main():
    S = input()
    Q = int(input())

    def insert(s,type):
        if type == 1:
            return s + S
        else:
            return S + s

    non_reverse = True
    for _ in range(Q):
        inp = input()
        if inp == "1":
            non_reverse = not non_reverse
        else:
            _,F,C = inp.split()
            F = int(F)
            if non_reverse:
                S = insert(C,F)
            else:
                S = insert(C,1 if F == 2 else 2)

    if non_reverse:
        print(S)
    else:
        print(S[::-1])



if __name__ == "__main__":
  main()


### FIXED CODE ###

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)

def main():
    S = input()
    Q = int(input())
    d = deque(list(S))
    rev = False

    def insert(x,f):
        g = f == "2" # append
        if rev:
            g = not g

        if g:
            d.append(x)
        else:
            d.appendleft(x)


    for q in range(Q):
        inp = input()
        if inp == "1":
            rev = not rev
        else:
            _,F,C = inp.split()
            insert(C,F)


    if rev:
        d.reverse()

    print("".join(d))



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

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

ab = [[int(l[0]), int(l[1])] for l in (input().split() for i in range(n))]
ab.sort()
temp = sum(ab, [])  # 疑似Flatten
a, b = temp[0::2], temp[1::2]

count, index, remainder = 0, 0, 0

for i in range(n):
  if count + b[i] < m:  
    count += b[i]
  else:
    index = i
    remainder = m - count
    
total = a[index] * remainder


total += sum([a[i] * b[i] for i in range(index)])


print(total)


### FIXED CODE ###

# cf. https://rion778.hatenablog.com/entry/2019/03/10/004006
import sys
input = sys.stdin.readline
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m < M:
      buy = min(M - m, plices[i][1])
      cost += plices[i][0] * buy
      m += buy
    else:
      break

print(cost)
### BUGGY CODE ###

import fractions as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   ans+=f.gcd(f.gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)
### BUGGY CODE ###

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

if N == 1:
  print(P)
  exit(0)
  
ans = 1
i = 2
while i ** N <= P:
  if P % i**N == 0:
    ans *= i
    P = P // i**N
    continue
  i += 1
  
print(ans)

### FIXED CODE ###

from math import floor
N, P = map(int, input().split())

if N == 1:
  print(P)
  exit(0)
  
ans = 1
#i = floor(pow(P,1/N))
#print(i)
i = 2

def prime_table(n):
  list = [True for _ in range(n + 1)]
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1

  table = [i for i in range(n + 1) if list[i] and i >= 2]
  return table

T = prime_table(floor(pow(P,1/N)))

for i in range(len(T)):
  if T[i] ** N > P:
    break
  while P % T[i]**N == 0:
    ans *= T[i]
    P = P // T[i]**N
  
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

def func(a, b):
    if dp[a][b]:
        return dp[a][b]

    for i in range(a, b+1, d):
        if a == b:
            dp[a][b] = 0
            return dp[a][b]
        elif i == a:
            dp[a][i] = 0
        else:
            dp[a][i] = dp[a][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

    for i in range(a, b+1, d):
        for j in range(i, b+1, d):
            dp[i][j] = dp[a][j]-dp[a][i]
    return dp[a][b]

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = func(a, b)
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

b = []
for num in a:
    b.append(target_num//num)
#b = [target_num//num for num in a]

print(sum(b) % (10**9+7))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

ans = 0
for i in range(n):
    ans += target_num//a[i]
#b = [target_num//num for num in a]

print(ans % (10**9+7))
### BUGGY CODE ###

mod=10**9+7
s=input()

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b

p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
d={i:0 for i in range(13)}
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1

    for i,v in enumerate(rev[num+1:]):
        #print(i+num+1)
        if v=="?":
            tmp=10**(i+num+1)%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
    #print(d)
    print(d[cal]%mod)
        



### FIXED CODE ###

#%%time
mod=10**9+7
s=input()


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    #print(i+num+1)
    if v=="?":
        t_d=[0 for _ in range(13)]
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])
### BUGGY CODE ###

N,W = map(int,input().split())
ls = []
for i in range(N):
    ls.append(list(map(int,input().split())))

dp = [[0]*(W+1) for i in range(N+1)]
# dp[i][j] はi-1番目までのものから重さj以下になるように選んだ最大値

for i in range(1,N+1):
    w,v = ls[i-1]
    for j in range(1,W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-w]+v)
            #ここでj-wを指定してしまっていいのか-> dp[i-1][j-w]>dp[i-1][j-w-1]であるので良い　j-wはそれ以下の最大値になっている
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])


### FIXED CODE ###

N,W = map(int,input().split())
ls = []
for i in range(N):
    ls.append(list(map(int,input().split())))

dp = [[0]*(W+1) for i in range(N+1)]
# dp[i][j] はi-1番目までのものから重さj以下になるように選んだ最大値

for i in range(1,N+1):
    w,v = ls[i-1]
    for j in range(1,W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-w]+v)
            #ここでj-wを指定してしまっていいのか-> dp[i-1][j-w]>dp[i-1][j-w-1]であるので良い　j-wはそれ以下の最大値になっている
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

from collections import Counter

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N = int(input())
matched = [False] * N
s = [None] * N
for i in range(N):
    s[i] = input()



ans = 0
i = 0
j = 1
cnt = 0
while i < N:
    cnt = 0

    if matched[i] == True:
        if i >= N-1:
            break
        
        i += 1
        j = i+1
        continue

    si = Counter(s[i])
    while j <= N-1:

        if matched[j] == True:
            j += 1

            continue


        sj = Counter(s[j])
        if si == sj:
            matched[i] = True
            matched[j] = True
            cnt += 1
        j += 1
    
    if cnt != 0:
        ans += cmb(cnt+1,2)

    if i == N-2:
        break

    i += 1
    j = i+1
    
print(ans)



### FIXED CODE ###

from collections import Counter

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


N = int(input())
matched = [False] * N
s = [None] * N
for i in range(N):
    moji = list(input())
    moji.sort()
    tmp = "".join(moji)
    s[i]= tmp

s.sort()
#print(s)
ans = 0
i = 0
j = 1
while i < N-1:
    cnt = 0
    #print("ss",i,j)
    if j == N:
        break
    while j <= N-1:
        #print("aa",i,j)
        if s[i] == s[j]:
            cnt += 1
            j += 1
            continue
        else:

            i = j
            j = i+1
            break
    if cnt >= 1:
        ans += cmb(cnt+1,2)
    

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

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
C = list(C.values())
C.sort()
n = len(C)
m = max(C)
S = [0]*(m+1)
b = 0
for i in range(n):
    c = C[i]
    if b<c:
        for j in range(b+1, c+1):
            S[j] = S[j-1]+(n-i)
        b = c
for i in range(1, N+1):
    ok = 0
    ng = N+1
    while ng-ok>1:
        mid = (ok+ng)//2
        if S[min(m, mid)]>=mid*i:#midが条件を満たすか
            ok = mid
        else:
            ng = mid
    print(ok)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
C = list(C.values())
C.sort()
n = len(C)
m = max(C)
S = [0]*(m+1)
b = 0
for i in range(n):
    c = C[i]
    if b<c:
        for j in range(b+1, c+1):
            S[j] = S[j-1]+(n-i)
        b = c
for i in range(1, N+1):
    ok = 0
    ng = N+1
    while ng-ok>1:
        mid = (ok+ng)//2
        if S[min(m, mid)]>=mid*i:#midが条件を満たすか
            ok = mid
        else:
            ng = mid
    print(ok)
### BUGGY CODE ###

S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    QUERY.append(input().split(' '))


def main(s, q, query):
    addflag = 'front'
    for i in range(q):
        if query[i][0] == '1':
            if addflag == 'front':
                addflag = 'back'
            elif addflag =='back':
                addflag = 'front'
        elif query[i][0] == '2':
            if addflag == 'front' and  query[i][1] == '1':
                s = query[i][2] + s
            elif addflag == 'front' and query[i][1] == '2':
                s = s + query[i][2]
            elif addflag == 'back' and  query[i][1] == '1':
                s = s + query[i][2]
            elif addflag == 'back' and  query[i][1] == '2':
                s = query[i][2] + s

    if addflag == 'back':
        s = ''.join(reversed(list(s)))

    return s


print(main(S, Q, QUERY))


### FIXED CODE ###

S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    QUERY.append(input().split(' '))


def main(s, q, query):
    addflag = 'front'

    s_front = ''
    s_back = ''

    for i in range(q):
        if query[i][0] == '1':
            if addflag == 'front':
                addflag = 'back'
            elif addflag == 'back':
                addflag = 'front'
        elif query[i][0] == '2':
            if addflag == 'front' and query[i][1] == '1':
                s_front = query[i][2] + s_front
                # s = query[i][2] + s
            elif addflag == 'front' and query[i][1] == '2':
                s_back = s_back + query[i][2]
                # s = s + query[i][2]
            elif addflag == 'back' and query[i][1] == '1':
                s_back = s_back + query[i][2]
                # s = s + query[i][2]
            elif addflag == 'back' and query[i][1] == '2':
                s_front = query[i][2] + s_front
                # s = query[i][2] + s

    if addflag == 'back':
        s = ''.join(reversed(list(s)))
        s_tmp = ''.join(reversed(list(s_front)))
        s_front = ''.join(reversed(list(s_back)))
        s_back = s_tmp

    return s_front + s + s_back


print(main(S, Q, QUERY))
### BUGGY CODE ###

#import sys
#sys.setrecursionlimit(10**8)
from collections import deque

n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]
visited = [False for _ in range(n)]
for _ in range(n+m-1):
	a, b = map(int, input().split())
	chil[a-1].append(b-1)
	rank[b-1] += 1

#print(chil)
for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1

def bfs(x):
	que = deque([[x, 0]])
	while que:
		l = que.pop()
		y, d = l[0], l[1]
		if d < depth[y]:
			continue
		for c in chil[y]:
			if depth[c] == -1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])
			elif depth[c] < d+1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])

	return

bfs(par)
#def dfs(x, d):
#	for c in chil[x]:
#		if depth[c] == -1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#		elif depth[c] < d+1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#
#	return
#
#dfs(par, 0)

for p in parent:
	print(p+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#from collections import deque

n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]
#visited = [False for _ in range(n)]
for _ in range(n+m-1):
	a, b = map(int, input().split())
	chil[a-1].append(b-1)
	rank[b-1] += 1

#print(chil)
for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1

#def bfs(x):
#	que = deque([[x, 0]])
#	while que:
#		l = que.pop()
#		y, d = l[0], l[1]
#		print(y, d)
#		if d < depth[y]:
#			continue
#		for c in chil[y]:
#			if depth[c] == -1:
#				depth[c] = d+1
#				parent[c] = y
#				que.appendleft([c, d+1])
#			elif depth[c] < d+1:
#				depth[c] = d+1
#				parent[c] = y
#				que.appendleft([c, d+1])
#
#	return

#bfs(par)

def dfs(x):
	true_chil = []
	for c in chil[x]:
		if rank[c] == 1:
			true_chil.append(c)
		else:
			rank[c] -= 1
	for t in true_chil:
		parent[t] = x
		dfs(t)

	return

dfs(par)

for p in parent:
	print(p+1)
### BUGGY CODE ###

num, K, *line = map(int, open(0).read().split())

dp = [float("inf")]* num
dp[0] = 0
 
for i in range(1, num):
  min_j = max(0, i - K)
  dp[i] = min([dp[j] + abs(line[i] - line[j]) for j in range(min_j , i)])

print(dp[-1])

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

def c_linear_approximation(N, A):
    t = [None for _ in range(len(A))]
    for j, k in enumerate(A):
        t[j] = k - (j+1)
    t_min, t_max = min(t), max(t)
    ans = float('inf')
    for b in range(-abs(t_min), abs(t_max)+1):
        tmp = 0
        for k in t:
            tmp += abs(k-b)
        ans = min(ans, tmp)
    return ans
N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))

### FIXED CODE ###

def c_linear_approximation(N, A):
    import numpy
    B = numpy.array([a-k for k, a in enumerate(A)])
    b = int(numpy.median(B))
    ans = 0
    for b_k in B:
        ans += abs(b_k - b)
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_linear_approximation(N, A))
### BUGGY CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p <= ai * ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        for k in range(lcm[p] - ps[i].get(p, 0)):
            prod = (prod * p) % mod
    ret = (ret + prod) % mod

print(ret)
        


### FIXED CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

lcmv = 1
for p in lcm:
    lcmv = (lcmv * (p ** lcm[p])) % mod

def inv(p, k):
    k = mod - k - 1
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = (ret * b) % mod
        b = (b * b) % mod
        k //= 2
    return ret

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = (prod * inv(p, ps[i][p])) % mod
    ret = (ret + prod) % mod

print(ret)
### BUGGY CODE ###

from collections import deque, Counter


def bfs(start, graph):
    q = deque([(start, 0)])
    visited = set()

    while q:
        curr, dist = q.popleft()
        if curr not in visited:
            yield start, curr, dist
            visited.add(curr)
            for neighbor in graph[curr]:
                q.append((neighbor, dist + 1))


if __name__ == '__main__':
    n, x, y = tuple([int(i) for i in input().split()])
    graph = {i: [] for i in range(1, n + 1)}

    for i in range(1, n):
        graph[i].append(i + 1)
        graph[i + 1].append(i)
    graph[min(x, y)].append(max(x, y))
    graph[max(x, y)].append(min(x, y))

    dists = [0 for k in range(n)]
    distances = {}
    for i in range(1, n):
        for s, e, d in bfs(i, graph):
            if s != e:
                start = min(s, e)
                end = max(s, e)
                key = (start, end)
                if key in distances.keys():
                    distances[key] = min(distances[key], d)
                else:
                    distances[key] = d

    dists = Counter(distances.values())

    for k in range(1, n):
        print(dists[k] if k in dists.keys() else 0)


### FIXED CODE ###

def distance(i, j, x, y):
    return min([abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(j - x)])


if __name__ == '__main__':
    n, x, y = tuple([int(i) for i in input().split()])
    x, y = min(x, y), max(x, y)

    dists = [0 for k in range(n)]
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            d = distance(i, j, x, y)
            dists[d] += 1

    for k in dists[1:]:
        print(k)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
D = {}
for a in A:
    bit = bin(a)[2:][::-1]
    for i in range(len(bit)):
        if bit[i] == '1':
            if i not in D:
                D[i] = 1
            else:
                D[i] += 1

ans = 0
for k, v in D.items():
    ans += (N-v)*v*2**k % mod
    ans = ans % mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
D = {}
for a in A:
    bit = bin(a)[2:][::-1]
    for i in range(len(bit)):
        if bit[i] == '1':
            if i not in D:
                D[i] = 1
            else:
                D[i] += 1

ans = 0
for k, v in D.items():
    ans += (N-v)*v*2**k % mod
    ans = ans % mod

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

import sys
sys.setrecursionlimit(10**7)

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

# 足場 i から 足場 N - 1 まで移動するときのコストの最小値
def rec(i):
    if i == N - 1:
        return 0
    elif i == N - 2:
        return rec(i + 1) + abs(h[i + 1] - h[i])
    else:
        return min(rec(i + 1) + abs(h[i + 1] - h[i]), rec(i + 2) + abs(h[i + 2] - h[i]))

print(rec(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

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

dp = [-1] * N # dp[i] := i から N-1 までの移動にかかる最小コスト
dp[N-1] = 0

def rec_memo(i):
    if dp[i] >= 0:
        return dp[i]
    
    if i == N-2:
        dp[i] = rec_memo(i+1) + abs(h[i+1] - h[i])
        return dp[i]
    else:
        dp[i] = min(rec_memo(i+1) + abs(h[i+1] - h[i]), rec_memo(i+2) + abs(h[i+2] - h[i]))
        return dp[i]

print(rec_memo(0))
### BUGGY CODE ###

from copy import copy
import random
import math
import sys
input = sys.stdin.readline
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(D)]
last = [0]*26
ans = [0]*D
score = 0
for i in range(D):
    ps = [0]*26
    for j in range(26):
        pl = copy(last)
        pl[j] = i+1
        ps[j] += s[i][j]
        for k in range(26):
            ps[j] -= c[k]*(i+1-pl[k])
    idx = ps.index(max(ps))
    last[idx] = i+1
    ans[i] = idx+1
    score += max(ps)
T = 3000
for k in range(42000):
    na = copy(ans)
    x = random.randint(1,365)
    y = random.randint(1,365)
    if x == y:
        continue
    na[x-1],na[y-1] = na[y-1],na[x-1]
    last = [0]*26
    ns = 0
    for i in range(D):
        last[na[i]-1] = i+1
        ns += s[i][na[i]-1]
        for j in range(26):
            ns -= c[j]*(i+1-last[j])
    if k%100 == 0:
        T *= 0.98
    p = pow(math.e,-abs(ns-score)/T)
    if ns > score or random.random() < p:
        ans = na
        score = ns
for a in ans:
    print(a)


### FIXED CODE ###

import random
for i in range(365):
  print(random.randint(1,26))