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

from functools import reduce
from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)


ans = reduce(lambda a, b: a+b, top_n_list)
print(ans)

### FIXED CODE ###

from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
ans = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)
    ans += top_n_list[i]

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

from functools import reduce
S = list(map(int,input().rstrip()))
l=len(S)
result=0
for i in range(l):
    for j in range(i+1,l+1):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %2019==0:
            result+=1
print(result)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from heapq import heappush, heappop
N, K = list(map(int, input().split()))

Alist = [int(i) for i in input().split(' ')]
import math



Alist=sorted(Alist, reverse=True)

 


def insert_list(list, value):
	start=0
	end=len(list)-1

	if value<list[len(list)-1]:
		list.insert(len(list), value)
		return list
	if value>list[0]:
		list.insert(0, value)
		return list
	while True:
		mid_point=int((start+end)/2)
		if value>list[mid_point]:
			if (end-start)<2:
				list.insert(start, value)
				return list
			else:
				end=mid_point
		else:
			if (end-start)<2:
				list.insert(end, value)
				return list
			else:
				start=mid_point

for i in range(K):
   if N==1:
      Alist[0]=Alist[0]/2**K
      break
   Alist[0]=Alist[0]/2
   
   if len(Alist)>1:
      value=Alist.pop(0)
      Alist=insert_list(Alist,value)
sum=0

for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

### FIXED CODE ###

from heapq import heappush, heappop
import math
 
N,M = [int(i) for i in input().split(' ')]
inputList = [int(i) for i in input().split(' ')]
list = []
 
for i in inputList:
    heappush(list, -i)
 
for _ in range(M):
    heappush(list, math.ceil(heappop(list)/2))
    
print(-sum(list))
### BUGGY CODE ###

x=input().split(" ")
n=int(x[0])
a=int(x[1])
b=int(x[2])
t=0
i=0
while t<=n:
    if t+a>n:
        i+=n-t
        break
    i+=a
    t+=a
    t+=b
print(i)


### FIXED CODE ###

def count_balls(n, a, b):
    if(a==0): return 0
    if(n<a): return n
    end = n % (a+b)
    if(end > a):
        return a*(n//(a+b))+a
    else:
        return a*(n//(a+b))+end
n,a,b=map(int, input().strip().split())
print(count_balls(n,a,b))
### BUGGY CODE ###

A,B,K=map(int,input().strip().split(" "))
c=[]

if(K>B):
    K=B

for i in range(K):
    if(A+i<=B):
        print(A+i)
    c.append(A+i)

for i in range(A):
    c.append(i)

if(B-K<=0):
    quit()


for i in range(B-K+1,B+1):
    if(i not in c and i<=B):
        print(i)


### FIXED CODE ###

A,B,K=map(int,input().strip().split(" "))
c=[]

if(A==B and K>=1):
    print(A)
    quit()
elif(A==B and K==0):
    quit()

if(B<=K):
    for i in range(A,B+1):
        print(i)
    quit()

else:

    if(K>B):
        K=B

    for i in range(K):
        if(A+i<=B):
            print(A+i)
        c.append(A+i)


    if(B-K<=0):
        quit()


    for i in range(B-K+1,B+1):
        if(i not in c and i<=B and i>=A):
            print(i)
### BUGGY CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = (3**N)%DIV

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())


### FIXED CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())
### BUGGY CODE ###

def main():
    import heapq
    hpop=heapq.heappop
    hpush=heapq.heappush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    visit=[False]*n
    h = []
    heapq.heapify(h)
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i=-i
        jj=(j+1)%n
        if visit[j]:
            if a[j-1]!=b[j-1]:
                print(-1)
                return 0
            visit[j-1]=True
            if a[jj]!=b[jj]:
                print(-1)
                return 0
            visit[jj]=True
            continue
        temp = i-a[j]
        temp2=b[j-1]+b[jj]
        sho=temp//temp2
        if sho==0:
            if a[j]!=b[j]:
                print(-1)
                return 0
            visit[j]=True
            if a[j-1]!=b[j-1]:
                print(-1)
                return 0
            visit[j-1]=True
            if a[jj]!=b[jj]:
                print(-1)
                return 0
            visit[jj]=True
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[input() for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(N, L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                if a+b > L[k]:
                    cnt += 1
    return cnt
print(solve(N, L))

### FIXED CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    txt = s[l-1:r]
    
    cnt = 0
    for j in range(len(txt)-1):
        if txt[j]=='A' and txt[j+1]=='C':
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

### FIXED CODE ###

from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

flg = []
for i in range(n-1):
    tmp_s = s[i:i+2]
    if tmp_s == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])
### BUGGY CODE ###

mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0]=1
for i in range(n):
    if s[i] == '?': 
        for j in range(10):
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13]+=dp[i][k] % mod
    else:
        for k in range(13): 
            dp[i + 1][(k * 10+ int(s[i])) % 13]+=dp[i][k] % mod
print(dp[-1][5] % mod)


### FIXED CODE ###

mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0]=1
for i in range(n):
    if s[i] == '?': 
        for j in range(10):
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13]+=dp[i][k] % mod
    else:
        for k in range(13): 
            dp[i + 1][(k * 10+ int(s[i])) % 13]+=dp[i][k] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

import itertools

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

l=list(itertools.combinations(L,3))
result = 0

for i in l:
    isOk=True
    a,b,c=i
    if a+b>c and a+c>b and c+b>a:
        result+=1

print(result)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()
 
result = 0

for aIndex,a in enumerate(L[:N-2]):
    for bIndex,b in enumerate(L[aIndex+1:N-1]):
        bIndex = aIndex + bIndex + 1
        ab = a+b
        n = bisect_left(L,ab) - bIndex - 1
        result += n
print(result)
### BUGGY CODE ###

n = int(input())
ans=1
for i in range(n+1):
    if i**2<=n:
        ans=i**2

print(ans)

### FIXED CODE ###

n = int(input())
ans=1
for i in range(n+1):
    if i**2<=n:
        ans=i**2
    else:
        break

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

S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

### FIXED CODE ###

S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
#        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
#        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))
### BUGGY CODE ###

def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s in range(n):
        if sum(costs[s]) == 0:
            continue
        for g in range(n):
            if costs[s][g] == 0:
                continue
            if s - d >= 0:
                costs[s][g] = costs[s - d][g] - costs[s - d][s]
                continue
            before = 0 if g - d < 0 else costs[s][g - d]
            costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                       index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])
### BUGGY CODE ###

def main2():
    n,k = map(int,input().split(" "))
    q = []
    for i in range(n):
        a,b = map(int,input().split(" "))
        q+=[a for j in range(b)]
    
    q.sort()
    print(q[k-1])

main2()

### FIXED CODE ###


def main2():
    import heapq
    n,k = map(int,input().split(" "))
    q = []
    for i in range(n):
        a,b = map(int,input().split(" "))
        heapq.heappush(q,(a,b))
    
    while k>0:
        a,b = heapq.heappop(q)
        k-=b
    
    print(a)
main2()
### BUGGY CODE ###

def judge(n):
    if n < 2:
        return False
    if n == 2 or n == 3 or n == 5 or n == 7 or n == 11 or n == 13 or n == 17 or n==19 or n==23 or n==29 or n==31 or n==37:
        return True
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0 or n % 13 == 0 or n % 17 == 0 or n%19==0 or n%23==0 or n%29==0 or n%31==0 or n%37==0:
        return False
    i = 19
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True


N = int(input())
count = 0
for i in range(N):
    if (judge(int(input())) == True):
        count += 1

print(count)

### FIXED CODE ###

import math


def judge(n):
    if n < 2:
        return False
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 1
    return True


count = 0
n = int(input())
for i in range(n):
    if judge(int(input())):
        count += 1
print(count)
### BUGGY CODE ###

def gcd(a,b):
    if b==0: return a
    return gcd(b,a%b)

k=int(input())
ans=0
for a in range(k):
    for b in range(k):
        for c in range(k):
            ans+=gcd(a+1,gcd(b+1,c+1))
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=gcd(a,gcd(b,c))
print(ans)
### BUGGY CODE ###

#d,t,s=map(int,input().split())
n=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=(A[i]%(10**9+7))*(A[j]%(10**9+7))
    ans%=(10**9+7)
print(ans)

### FIXED CODE ###

import itertools
#h,w=map(int,input().split())
#S=[list(map(int,input().split())) for _ in range(h)]
n=int(input())
A=list(map(int,input().split()))
Ar=list(itertools.accumulate(A))
ans=0
for i in range(n-1):
    ans+=A[i]*(Ar[n-1]-Ar[i])
    ans%=10**9+7
print(ans)
### BUGGY CODE ###

n=int(input())
l=sorted([int(i) for i in input().split()],reverse=True)

#print(l)
co=0
for i in range(n-2):
    c=l[i]
    x=0
    for j in range(i+1,n-1):
        b=l[j]
        for k in range(j+1,n):
            a=l[k]
            if c<(a+b):
                co+=1
            else:
                if k==j+1:
                    x=1
                break
        if x==1:
            break

print(co)

### FIXED CODE ###

from bisect import bisect_left

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

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

import math

n=int(input())
c=0
for i in range (1,n):
    d=0
    for j in range (1,int(math.sqrt(i))+1):
        if i%j==0:
            d+=1
            if j*j!=i:
                d+=1
    c+=d
print(c)

### FIXED CODE ###

import math
 
n = int(input())
cnt = 0
for i in range(1, n):
    cnt += (n-1) // i
print(cnt)
### BUGGY CODE ###

A,B,K=map(int,input().split())
while K!=0:
  if A>=1:
    A-=1
    K-=1
  else:
    B-=1
    K-=1
print(A,' ',B)

### FIXED CODE ###

A,B,K=map(int,input().split())
if K>=A:
  K=K-A
  if K>=B:
    K=K-B
    print('0 0')
  else:
    B=B-K
    print(0,' ',B)
else:
  print(A-K,' ',B)
### BUGGY CODE ###

import sys
import math

n,m=map(int,input().split())
n_comb=math.factorial(n)
m_comb=math.factorial(m)

if abs(n-m)>=2:
  print(0)
  sys.exit()
elif n==m:
  print(n_comb*m_comb*2)
  sys.exit()
else:
  print(n_comb*m_comb)
  

### FIXED CODE ###

n, m = map(int, input().split())
MOD = 1000000007
 
def fac(n):
    ans = 1
    for i in range(1, n + 1):
        ans = (ans * i) % MOD
    return ans
 
if abs(m - n) > 1:
    print(0)
elif m == n:
    print((2 * fac(m) * fac(n)) % MOD)
else:
    print((fac(m) * fac(n)) % MOD)
### BUGGY CODE ###

# coding: utf-8

import sys

N, M = map(int, sys.stdin.readline().split(" ", 2))

L = []
R = []

ans = { i:0 for i in range(N)}
anss = []
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    for i in range(l, r+1):
        ans[i-1] += 1
print(sum(1 for a in ans.values() if a == M))

### FIXED CODE ###

# coding: utf-8

import sys
import numpy as np

N, M = map(int, sys.stdin.readline().split(" ", 2))

L = 0
R = M + N
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    if l > L:
        L = l
    if r < R:
        R = r
print(max(0, R - L + 1))
    # L.append(l)
    # R.append(r)
### BUGGY CODE ###

#C
L, R = list(map(int, input().split()))
result = 2018
for i in range(L,R+1):
    for s in range(i+1,R+1):
        x = (i*s)%2019
        if x == 0:
            result = 0
        if result > x:
            result = x
print(result)

### FIXED CODE ###

#C
import sys
L, R = list(map(int, input().split()))
if (R - L) == 2019:
    result = 0
else:
    result = 2018
    for i in range(L,R+1):
        for s in range(i+1,R+1):
            x = (i*s)%2019
            if x == 0:
                result = 0
                print(0)
                sys.exit()
            elif result > x:
                result = x
print(result)
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1,n+1):
    p *= i

a = p % (10**9 + 7)
print(a)

### FIXED CODE ###

N = int(input())

result = 1
for i in range(1,N+1):
    result *= i
    result %= 10**9+7
print(result)