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

import threading
import sys
import functools


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

    @functools.lru_cache(maxsize=None)
    def solve(stock: int, money: int, day: int, end_day: int) -> int:
        if end_day == day:
            return money

        current_price = A[day]

        money_buy = money - (money // current_price) * current_price
        stock_buy = (money // current_price) + stock

        money_sell = money + stock * current_price
        stock_sell = 0

        return max(
            solve(stock, money, day + 1, end_day),
            solve(stock_buy, money_buy, day + 1, end_day),
            solve(stock_sell, money_sell, day + 1, end_day),
        )

    print(solve(0, 1000, 0, N))


if __name__ == "__main__":

    sys.setrecursionlimit(1024 * 1024 * 2)
    threading.stack_size(128 * 1024 * 1024 * 2)
    threading.Thread(target=main).start()


### FIXED CODE ###

from typing import List


def solve(A: List[int], N: int) -> int:
    current_money = 1000
    for i in range(N - 1):
        stocks = 0

        if A[i] < A[i + 1]:
            stocks = current_money // A[i]
        current_money += (A[i + 1] - A[i]) * stocks
    return current_money


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

    print(solve(A, N))


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

N = int(input())
A = list(map(int, input().split()))
num_list = [0] * 100
P = 10 ** 9 + 7
for i in A:
    tmp = i
    for j in range(len(bin(i)) - 2):
        num_list[j] += (tmp & 1)
        tmp = tmp >> 1
ans = 0


def func(N, n):
    return (N - n) * n


for i in range(100):
    ans = (ans + func(N, num_list[i]) * 2 ** i) % P
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
num_list = [0] * 100
P = 10 ** 9 + 7
for i in A:
    tmp = i
    for j in range(len(bin(i)) - 2):
        num_list[j] += (tmp & 1)
        tmp = tmp >> 1
ans = 0


def func(N, n):
    return (N - n) * n


for i in range(100):
    ans = (ans + func(N, num_list[i]) * 2 ** i) % P
print(ans)
### BUGGY CODE ###

import math
N = int(input())
S = input()
ans = 1
ans_base = 1
numofS = 0  # 線の左端になっている点をSとするとその数はちょうどNでないといけない
line = 0  # 左から順に線を引く。上に何本通っているかをあらわす
for i in range(2*N):
    if S[i] == "B":
        if line % 2 == 0:
            numofS += 1
            line += 1
        else:
            ans_base *= line
            line -= 1
    else:
        if line % 2 == 0:
            ans_base *= line
            line -= 1
        else:
            line += 1
            numofS += 1

    if line < 0:
        ans = 0
if numofS != N:
    ans = 0
    # print(numofS)

if ans != 0:
    fact = math.factorial(N)
    ans = ans_base * fact
    ans %= 10**9+7
print(ans)


### FIXED CODE ###

import math
N = int(input())
S = input()
ans = 1
ans_base = 1
numofS = 0  # 線の左端になっている点をSとするとその数はちょうどNでないといけない
line = 0  # 左から順に線を引く。上に何本通っているかをあらわす
for i in range(2*N):
    if S[i] == "B":
        if line % 2 == 0:
            numofS += 1
            line += 1
        else:
            ans_base *= line
            line -= 1
    else:
        if line % 2 == 0:
            ans_base *= line
            line -= 1
        else:
            line += 1
            numofS += 1

    if line < 0:
        ans = 0
        break
    ans_base %= 10**9+7
if numofS != N:
    ans = 0
    # print(numofS)

if ans != 0:
    fact = math.factorial(N)
    fact %= 10**9+7
    ans = ans_base * fact
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(reverse=True, key=lambda x: x[1])

count = lambda A, C: sum(a < C for a in A)

A.sort()
for B, C in opes:
    if A[0] >= C:
        break
    li = [C for _ in range(min(B, count(A, C)))]
    A = A[len(li):] + li

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
opes = [tuple(map(int, input().split())) for _ in range(M)]
opes.sort(key=lambda x:-x[1])

D = []
lenD = 0
for B, C in opes:
    D += [C]*B
    lenD += B
    if lenD >= N:
        break

A.sort()
for i, d in enumerate(D[:N]):
    if A[i] >= d:
        break
    A[i] = d

print(sum(A))
### BUGGY CODE ###

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]*A[j]%(10**9+7)
        ans%=(10**9+7)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
tmp=0
for i in range(N):
    tmp+=A[i]
    
for i in range(N):
    tmp-=A[i]
    ans+=A[i]*tmp%(10**9+7)
    ans%=(10**9+7)
print(ans)
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
n = 1
m = 1
aa = a/2

c = 0
d = 0

if a%2 == 1:
    aa = (aa*2+1)//2

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()
    
for i in range(int(aa)):
  n = n * b[i]

for i in range(int(aa),a):
    m *= b[i]

if n * m <= 10**18:
    print(n*m)
    exit()
  
print('-1')

### FIXED CODE ###

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

c = 0
d = 0

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()

for i in b:
  n *= i
  if n > 10**18:
    print(-1)
    exit()
print(n)
### BUGGY CODE ###

from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 18

        dp = [[[inf]*4 for _ in range(w+2)] for _ in range(h+2)]
        dp[xs][ys][0] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)

            if cost > dp[x][y][dirt]:
                continue

            if (x, y) == (xg, yg):
                ans = (dp[x][y][dirt] + (-dp[x][y][dirt]) % k)//k
                return ans

            for i in range(4):
                nx, ny = x + direction[i][0], y + direction[i][1]
                if field[nx][ny]:
                    if i == dirt:
                        if dp[nx][ny][i] > dp[x][y][i] + 1:
                            dp[nx][ny][i] = dp[x][y][i] + 1
                            heappush(que, (dp[nx][ny][i], nx, ny, i))
                    else:
                        if dp[x][y][i] > dp[x][y][dirt] + (-dp[x][y][dirt])%k:
                            dp[x][y][i] = dp[x][y][dirt] + (-dp[x][y][dirt])%k
                            heappush(que, (dp[x][y][i], x, y, i))
        return -1


    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    for a in A:
        if a < 0:
            limit_pair = -(-num // a)
            limit_idx = np.searchsorted(A, limit_pair, side='left')
            if a ** 2 <= num:
                less_count -= 1
            less_count += n - limit_idx
        
        elif a == 0:
            if num >= 0:
                less_count += n-1
        
        elif a > 0:
            limit_pair = num // a
            limit_idx = np.searchsorted(A, limit_pair, side='right')
            if a ** 2 <= num:
                less_count -= 1
            less_count += limit_idx
    
    less_count //= 2
    if less_count >= k:
        right = num
    else:
        left = num

print(right)

### FIXED CODE ###

import numpy as np

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

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A==0).sum()

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num >= 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(num // -negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)
### BUGGY CODE ###

#D
N, K = map(int, input().split())
p= [int(x) for x in input().split()]
ap = p
ans = 0
for i in range(N):
    ap[i] = (p[i]+1)/2
for i in range(N-K+1):
    now = 0
    for j in range(K):
        now += ap[i+j]
    ans = max(ans, now)

print (ans)

### FIXED CODE ###

#D
N, K = map(int, input().split())
p= [int(x) for x in input().split()]
ap = p
ans = 0
for i in range(N):
    if i == 0:
        ap[i] = (p[i]+1)/2
    else:
        ap[i] = (p[i]+1)/2 + ap[i-1]
for i in range(N-K+1):
    now = 0
    if i == 0:
        now = ap[K-1]
    else:
        now = ap[K+i-1]-ap[i-1]
    ans = max(ans, now)

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

import numpy as np
N=int(input())
A=list(map(int,(input().split())))
npArray = np.array(A)
npArray=npArray.copy()
ans=np.sum(npArray)
Q=int(input())

for i in range(Q):
  L, R = map(int,(input().split()))
  B_count=np.count_nonzero(npArray == L)
  sa=(R-L)*B_count
  #npArray = np.where(npArray == L,R, npArray)
  npArray[npArray == L] = R
  ans= ans+sa
  print(ans)



### FIXED CODE ###

import collections
import copy
N=int(input())
A=list(map(int,(input().split())))
ans=sum(A)
Q=int(input())
col = collections.Counter(A)

for i in range(Q):
  L, R = map(int,(input().split()))
  sa=(R-L)*col[L]
  col[R]+=copy.copy(col[L])
  col[L]=0
  ans= ans+sa
  print(ans)
### BUGGY CODE ###

n = int(input())
A = list()
for i in range(0, n):
    A.append(int(input()))

G = [1]
cnt = 0

for l in range(1, 100):
    h = 3 * G[l - 1] + 1
    if(h > n):
        m = l
        break
    else:
        G.append(3*G[l-1] + 1)
for g in reversed(G):
    for t in range(g, n):
        v = A[t]
        j = t - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v


print(m)
print(" ".join(str(x) for x in reversed(G)))
print(cnt)

print("\n".join(str(x) for x in A))

### FIXED CODE ###

n = int(input())
A = list()
G = [1]
cnt = 0

for i in range(0, n):
    A.append(int(input()))


def insertion_sort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


# G[i] = 3*Gi-1 + 1
def shell_sort():
    for i in range(1, 101):
        h = 3 * G[0] + 1
        if h > n:  # h???n?¶???????????????§?????????4n+3*2n-1+1
            break
        else:
            G.insert(0, h)
    for g in G:
        insertion_sort(A, n, g)

shell_sort()
print(len(G))
print(" ".join(str(x) for x in G))
print(cnt)
print("\n".join(str(x) for x in A))
### BUGGY CODE ###


s=list(input())


l=0
r=len(s)-1

count=0
while True:
    #print(s,l,r)
    if s[l]!=s[r]:
        if s[l]=="x":
            #s.insert(r+1,"x")
            l+=1
        elif s[r]=="x":
            s.insert(l,"x")
            #r-=1
            l+=1
        else:
            res=-1
            break

        #print(s,l,r)


        count+=1
    else:
        r-=1
        l+=1

    if l>=r:
        res=count
        break


print(res)

### FIXED CODE ###


s=list(input())


l=0
r=len(s)-1

count=0
while True:
    #print(s,l,r)
    if s[l]!=s[r]:
        if s[l]=="x":
            #s.insert(r+1,"x")
            l+=1
        elif s[r]=="x":
            #s.insert(l,"x")
            r-=1
            #l+=1
        else:
            res=-1
            break

        #print(s,l,r)


        count+=1
    else:
        r-=1
        l+=1

    if l>=r:
        res=count
        break


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

N=int(input())
S=list(input())
count = N
for i in range(N):
  x=S[:i].count('W')+S[(i+1):].count('E')
  if count > x:
    count = x
print(count)

### FIXED CODE ###

N=int(input())
S=list(input())
C=[0]*N
C[0]=S[1:].count('E')
for i in range(1,N):
  C[i]=C[i-1]+ (S[i-1]=='W')-(S[i]=='E') 
print(min(C))
### BUGGY CODE ###

def resolve():
    s = input()
    k = int(input())
    l = len(s)
    subs = set(s)
    for i in range(l):
        for j in range(i + 1, l + 1):
            sub = s[i:j]
            subs.add(sub)
    print(sorted(subs)[k - 1])


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    s = input()
    k = int(input())
    l = len(s)
    subs = []
    for i in range(l):
        for j in range(i + 1, i + k + 1):
            sub = s[i:j]
            if sub not in subs:
                subs.append(sub)
    print(sorted(set(subs))[k - 1])


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

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ban=[]
    h,w=INTM()
    for i in range(h):
        s=STR()
        ban.append(s)
    left =np.zeros((h,w),dtype='int')
    right=np.zeros((h,w),dtype='int')
    up   =np.zeros((h,w),dtype='int')
    down =np.zeros((h,w),dtype='int')
    #print(up)
    for i1 in range(h):
        for i2 in range(w):
            i3=(w-1)-i2
            i4=(h-1)-i1
            if ban[i1][i2]=="#":
                left[i1][i2]=0
                up[i1][i2]=0
            else:
                if i1==0:
                    up[i1][i2]=1
                else:
                    up[i1][i2]=up[i1-1][i2]+1

                if i2==0:
                    left[i1][i2]=1
                else:
                    left[i1][i2]=left[i1][i2-1]+1
            if ban[i1][i3]=="#":
                right[i1][i3]=0
            else:
                if i2==0:
                    right[i1][i3]=1
                else:
                    right[i1][i3]=right[i1][i3+1]+1    

            if ban[i4][i2]=="#":
                down[i4][i2]=0
            else:
                if i1==0:
                    down[i4][i2]=1
                else:
                    down[i4][i2]=down[i4+1][i2]+1
    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

### FIXED CODE ###

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    h,w=INTM()
    ban=np.zeros((h,w),dtype=np.int16)
    for i in range(h):
        s=STR()
        for i1 in range(len(s)):
            if s[i1]==".":
                ban[i][i1]=1

    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    #print(up)
    for i in range(w):
        i2=w-1-i
        if i==0:
            left[:,i]=ban[:,i]
            right[:,i2]=ban[:,i2]
        else:
            left[:,i]=ban[:,i]*(left[:,i-1]+1)
            right[:,i2]=ban[:,i2]*(right[:,i2+1]+1)
    
    for i in range(h):
        i2=h-1-i
        if i==0:
            up[i,:]=ban[i,:]
            down[i2,:]=ban[i2,:]
        else:
            up[i,:]=ban[i,:]*(up[i-1,:]+1)
            down[i2,:]=ban[i2,:]*(down[i2+1,:]+1)
    

    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


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

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

for i in range(N):
  	A[i] = A[i] % (10 ** 9 + 7)

res = 0

for i in range(N-1):
    for j in range(i+1, N):
        res += (A[i] * A[j]) % (10 ** 9 + 7)
        res = res % (10 ** 9 + 7)
print(res)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
ans = 0

A_sum = [A[0] for i in range(N)]
for i in range(1, N):
    A_sum[i] = A_sum[i-1] + A[i]

for i in range(1, N):
    ans += A[i] * A_sum[i-1]
    ans %= mod

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

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d1 = deque()
d.append((Ch, Cw))
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2,-1,0,1,2]
while True:
  # 行けるところすべて追加
  targets = set()
  while len(d) > 0:
    temps = set(d)
    targets |= temps
    d = deque()
    for Th, Tw in temps:
      for i,j in a:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          s.add((Th,Tw))
  # クリアしてるか確認
  if (Dh,Dw) in targets:
    print(ans)
    exit()
  else:
    d = deque()
    ans += 1
    for Th,Tw in targets:
      for i in b:
        for j in b:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
            s.add((Th,Tw))
    if len(d) == 0:
      print('-1')
      exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

from heapq import heappop, heappush
from collections import defaultdict

INF = 10**20
N,M = map(int,input().split(' '))
g = defaultdict(set)
cost = defaultdict(lambda : INF)
lmin = [N+1] * (N+1)
LRC = []
for i in range(1,M+1):
    l,r,c = list(map(int,input().split(' ')))
    for j in range(l,r):
        g[j].add(r)
        cost[(j,r)] = min(cost[(j,r)],c)

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t in g[s]:
        c = cost[(s,t)]
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
        



### FIXED CODE ###

import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.buffer.readline

INF = 10**20
N,M = map(int,input().split())
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split()))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
### BUGGY CODE ###

from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

print(ans)


### FIXED CODE ###

from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i, 2019)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

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

n = int(input())
sum = 0
 
def gcd(a, b, c):
    smaller = min(min(a, b), c)
    for i in range(1, smaller + 1):
        if (a % i == 0) and (b % i == 0) and (c % i == 0):
            gcd = i
    return gcd
 
for i in range (1, n + 1):
    for j in range (1, n + 1):
        for k in range(1, n + 1):
            sum += gcd(i, j, k)
print(sum)

### FIXED CODE ###

n = int(input())
sum = 0

def gcd(a, b):
    if a < 1 or b < 1 :
        if a > 0:
            return a
        return b
    remainder = 0
    if a % b == 0 :
        return b
    remainder = a % b
    a = b
    b = remainder
    return gcd(a, b)

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i, j), k)
print(sum)