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

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = format(a[i], 'b')
    k = list(k)
    k.reverse()
    for s in range(leng - len(k)):
        k.append(0)
    for j in range(leng):
        if k[j] == "1":
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

dp = [[[] for _2 in range(s + 1)] for _1 in range(n)]

for i, ai in enumerate(a):
  if ai <= s:
    dp[i][ai].append((i, i))
  if i > 0:
    for j, t in enumerate(dp[i-1]):
      for r, l in t:
        dp[i][j].append((r, l))
        if j + ai <= s:
          dp[i][j + ai].append((r, i))
        
print(sum((r + 1) * (n - l) for r, l in dp[n-1][s]))
    

### FIXED CODE ###

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

dp = [[1 if _2 == 0 else 0 for _2 in range(s + 1)] for _1 in range(n+1)]

MOD = 998244353

for i, ai in enumerate(a):
  for j, v in enumerate(dp[i]):
    dp[i + 1][j] += v
    dp[i + 1][j] %= MOD 
    if j + ai <= s:
      dp[i + 1][j + ai] += v
      dp[i + 1][j + ai] %= MOD


print(sum(dp_i[s] for dp_i in dp) % MOD)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ctr=0
el=[]
for i in range(n):
    if a[i] not in el:
        num=a.count(a[i])
        el.append(a[i])
        if a[i]>num:
            ctr+=num
        else:
            ctr+=num-a[i]
print(ctr)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ctr=1
ln=[]
for i in range(n-1):
    if a[i]==a[i+1]:
        ctr+=1
    elif a[i]!=a[i+1]:
        ln.append([a[i],ctr])
        ctr=1
ln.append([a[n-1],ctr])
ans=0
for k in range(len(ln)):
    if ln[k][0]>ln[k][1]:
        ans+=ln[k][1]
    else:
        ans+=ln[k][1]-ln[k][0]
print(ans)
### BUGGY CODE ###

n, a, b = map(int,input().split())
mod = 10**9+7

def rev(x):
    re = 10**9+5
    num = 1
    ix = x
    while re > 0:
        if re%2 == 1:
            num = (num*ix)%mod
        re //= 2
        ix = (ix**2)%mod
    return(num)

kaijo = [0 for i in range(n+1)]
kaijo[0] = 1
for i in range(1,n+1):
    kaijo[i] = (kaijo[i-1]*i)%mod

re = n
ans = 1
i2 = 2
while re > 0:
    if re%2 == 1:
        ans = (ans*i2)%mod
    re //= 2
    i2 = (i2**2)%mod

ans -= 1
ans = (ans - (((kaijo[n]*rev(kaijo[a]))%mod)*rev(kaijo[n-a]))%mod)%mod
ans = (ans - (((kaijo[n]*rev(kaijo[b]))%mod)*rev(kaijo[n-b]))%mod)%mod
print(ans)


### FIXED CODE ###

n, a, b = map(int,input().split())
mod = 10**9+7

def rev(x):
    re = 10**9+5
    num = 1
    ix = x
    while re > 0:
        if re%2 == 1:
            num = (num*ix)%mod
        re //= 2
        ix = (ix**2)%mod
    return(num)

def kaijo(x):
    num = 1
    for i in range(1,x+1):
        num = (num*i)%mod
    return(num)

re = n
ans = 1
i2 = 2
while re > 0:
    if re%2 == 1:
        ans = (ans*i2)%mod
    re //= 2
    i2 = (i2**2)%mod
nca = 1
ncb = 1
for i in range(a):
    nca = (nca*(n-i))%mod
for i in range(b):
    ncb = (ncb*(n-i))%mod

ans -= 1
ans = (ans-(nca*rev(kaijo(a)))%mod)%mod
ans = (ans-(ncb*rev(kaijo(b)))%mod)%mod

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

def resolve():
    n,k,q=map(int,input().split())
    a=[int(input()) for _ in range(q)]
    pnt=[k]*n
    for i in range(q):
        for k in range(n):
            pnt[k]-=1 if k!=a[i]-1 else 0
    for i in range(n):
        print('Yes' if pnt[i]>0 else 'No')
resolve()

### FIXED CODE ###

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

n = int(input())
A = list(map(int, input().split()))
s = 0
while True:
    for i in range(n):
        if (A[i] // 2 == 1) or (A[i] == 0):
            break
    for j in range(n):
        A[j] = A[j] / 2
    s+=1
print(s)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
s = 0

def count(A, n):
    for i in range(n):
        if (A[i] % 2 == 1) or (A[i] == 0):
            return False
        A[i] = A[i] // 2
    return True

while True:
    if count(A, n):
        s += 1
    else:
        break
    
print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

lc = [0]
for aa in a:
    lc.append(gcd(lc[-1], aa))

if lc[-1] != 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


if a[-1]==1:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(n)

count = [0]*len(prime_numbers_list)

for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            if count[i]==2:
                print('setwise coprime')
                exit()
            break

print('pairwise coprime')




### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10

def eratosthenes3(limit):
    sieve = [i for i in range(limit+1)]
    p = 2
    while p*p <= limit:
        if sieve[p] == p:
            for q in range(2*p,limit+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    return sieve

sieve = eratosthenes3(MAXN)

st = set()
for aa in a:
    tmp = set()
    while aa > 1:
        tmp.add(sieve[aa])
        aa //= sieve[aa]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = []
for i in range(h):
    a.append(input())
b = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b.append([i, j])

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            tmp = inf
            for x in b:
                tmp = min(tmp, abs(i-x[0])+abs(j-x[1]))
            ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split())
person = np.asarray([K] * N)

for i in range(Q):
    ok_person = int(input()) - 1
    person -= 1
    person[ok_person] += 1

for i in range(N):
    if person[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split())
person = np.asarray([K] * N)

ok_person = [int(input()) for i in range(Q)]
false_num = len(ok_person)
person -= false_num
#print(person)
for i in ok_person:
    person[i-1] += 1
#    print(person)

#print(person)

for i in range(N):
    if person[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
Alst = list(map(int, input().split()))
ans = 0
l = len(Alst)
for i in range(l):
    ans = (ans + Alst[i]*sum(Alst[i+1:]))%(10**9 +7)

print(ans)

### FIXED CODE ###

N = int(input())
Alst = list(map(int, input().split()))
l = len(Alst)
Blst = [0]*l
k = 0
ans = 0
for i in range(l-1, 0, -1):
    k = (k + Alst[i])%(10**9 + 7)
    Blst[i] = k

for j in range(l-1):
    ans = (ans + Alst[j] * Blst[j+1])%(10**9 + 7)

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

s = input()
ans = 0
while True:
  st1 = s.split("01")
  st2 = ("".join(st1)).split("10")
  if len(st1)==1 and len(st2)==1:
    break
  ans += len(st1)-1+len(st2)-1
  s = "".join(st2)
print(ans*2)

### FIXED CODE ###

a,b=0,0
for s in input():
  if s=="0": a+=1
  else: b+=1
print(min(a,b)*2)
### BUGGY CODE ###

n  = int(input())
s = [int(input()) for i in range(n)]


ans = 0
for i in range(0,2**n):
    bits = (bin(i)[2:]).zfill(n)
    tmp = sum([j * int(k) for j, k in zip(s, bits)])
    ans = max(ans, tmp if tmp % 10 != 0 else 0)

print(ans)

### FIXED CODE ###

n  = int(input())
s = [int(input()) for i in range(n)]

s.sort()
ans = sum(s)
if (ans % 10 != 0):
    print(ans)
else:
    for i in s:
        if (i % 10 != 0):
            print(ans - i)
            break
    else:
        print(0)
### BUGGY CODE ###

#D
import itertools
N=int(input())
S=str(input())
S_list=list(S)
password_list=[]
for x in itertools.product(['0','1','2','3','4','5','6','7','8','9'],repeat=3):
  for i in range(N-2):
    if x[0]==S_list[i]:
      for j in range(i+1,N-1):
        if x[1]==S_list[j]:
          for k in range(j+1,N):
            if x[2]==S_list[k]:
              password_list +=[''.join(x)]
              break
answer=len(set(password_list))
print(answer)

### FIXED CODE ###

#D
import itertools
N=int(input())
S=str(input())
count=0
for i,j,k in itertools.product(range(10),repeat=3):
  try:
    x = S.index(str(i))
    y = S.index(str(j),x+1)
    z = S.index(str(k),y+1)
    count +=1
  except:
    continue

print(count)
### BUGGY CODE ###






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


"""
たとえばSが 123456789 だとすると
3456 = (3456789 - 789) // 1000
と表せる。
これがPで割り切れる場合、基本的には 3456789 と 789 がPで割り切れるとよい。
これはPと 10**x が互いに素の場合。
なので、10**x とPが互いに素の場合は、
・S[l:]をPで割った時余りがXXXになるものが何個、という情報を、Sの右端から集めていく。ただし、
・あるindexのlのS[l:]を見ているときに、その部分をPで割って余りがKになるなら、そのlに対してlより右にあるrについて、
　S[r:]をPで割った余りがKになるようにrを選んでS[l:r]を作ると、Pで割り切れる数字が得られる。その時点でのmod P = Kの個数に対応する。
　ただし、rに何も選ばない場合（lから端までを数字にする場合）もあるので、これも考慮に入れる。

Pが10と互いに素でない場合は、2と5がありうる。
これについて、それぞれ末尾が2の倍数か5の倍数であれば割り切れるので、
Sを左から見ていって、その数字が見つかれば、そのindexをふくむ左の位置で数字を作ればPで割れる数字ができる
"""

ans = 0
if P in [2, 5]:
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1

else:
    mod_P = [0] * P
    mod_P[0] += 1

    curr = 0
    for i in range(N):
        curr += int(S[N-1-i]) * 10**i
        ans += mod_P[curr % P]
        mod_P[curr % P] += 1

print(ans)

### FIXED CODE ###




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

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)
### BUGGY CODE ###

from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        # M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
A = inpl()
#N = 10**4
#A = [randint(0, 10**6) for _ in range(10**4)]

lcm = 1
for a in A:
    lcm = a * lcm // gcd(a, lcm)
ans = 0
for i in range(N):
    ans += lcm // A[i]
print(ans%MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


P = primes(10**3)

size = 10**6 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 

N = int(input())
A = inpl()

#N = 10**4
#A = [randint(0, 10**6) for _ in range(10**4)]
D = defaultdict(int)
for a in A:
    for p in P:
        tmp = 0
        while a%p == 0:
            tmp += 1
            a //= p
        if tmp:
            D[p] = max(D[p], tmp)
        if a == 1:
            break
    if a != 1:
        D[a] = 1

lmc = 1
for k, v in D.items():
    lmc = lmc * pow(k, v, MOD)%MOD

ans = 0
for a in A:
    ans = (ans + lmc*inverse[a])%MOD
print(ans)
### BUGGY CODE ###

num = [i for i in range(0,100001)]

for j in range(1,100001):
        num[j] = j//6 + num[j%6]

for j in range(1,100001):
        num[j] = min(num[j],j//9+num[j%9])

for j in range(1,100001):
        num[j] = min(num[j],j//36+num[j%36])

for j in range(81,324):
        num[j] = min(num[j],1+num[j-81])
for j in range(162,324):
        num[j] = min(num[j],2+num[j-162])
for j in range(243,324):
        num[j] = min(num[j],3+num[j-243])
for j in range(324,100001):
        num[j] = (j//324)*4 + num[j%234]

for j in range(216,648):
        num[j] = min(num[j],1+num[j-216])
for j in range(432,648):
        num[j] = min(num[j],2+num[j-216*2])
for j in range(648,100001):
        num[j] = (j//648)*3 + num[j%648]

for i in range(1,8):
        for j in range(729*i,729*8):
                num[j] = min(num[j],i+num[j-729*i])
for j in range(729*8,100001):
        num[j] = (j//(729*8))*8+num[j%(729*8)]

MoneyYouCanGet = [6**4,9**4,6**5,6**6,9**5]

for i in MoneyYouCanGet:
        for j in range(1,100001):
                k = 1
                while k*i<j:
                        num[j] = min(num[j],k+num[j-k*i])
                        k += 1

N = int(input())
print(num[N])

### FIXED CODE ###

SixNum = [i for i in range(0,100001)]
for i in range(1,7):
        for j in range(1,100001):
                SixNum[j] = min(SixNum[j],j//(6**i) + SixNum[j%(6**i)])

NineNum = [i for i in range(0,100001)]
for i in range(1,6):
        for j in range(1,100001):
                NineNum[j] = min(NineNum[j],j//(9**i) + NineNum[j%(9**i)])

N = int(input())
ans = 100001
for i in range(0,N+1):
        ans = min(ans,SixNum[i]+NineNum[N-i])
print(ans)
### BUGGY CODE ###

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

max_pos = 0
max_value = 0
for i in range(len(P)):
    tmp_sum = sum(P[i:i+K])
#    print(i, tmp_sum, P[i:i+K])
    if tmp_sum > max_value:
        max_value = tmp_sum
        max_pos = i

#print("--------", max_pos)
total = 0
for i in range(max_pos, max_pos + K):
    total += sum(list(range(1, P[i] + 1))) / P[i]
#    print(i, total, sum(list(range(1, P[i] + 1))) / P[i])

print(total)


### FIXED CODE ###

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

max_pos = 0
max_value = sum(P[:K])
tmp_sum = max_value
for i in range(N-K):
    tmp_sum = tmp_sum - P[i] + P[i+K]
#    print(i, max_value, tmp_sum, P[i:i+K], "-", P[i], "+", P[i+K])
    if tmp_sum > max_value:
        max_value = tmp_sum
        max_pos = i + 1

#print("--------", max_pos)
total = 0
for i in range(max_pos, max_pos + K):
    total += (P[i] + 1) / 2
#    print(i, total, sum(list(range(1, P[i] + 1))) / P[i])

print(total)
### BUGGY CODE ###

L, R = map(int, input().split())

tmp = R - L + 1
if tmp >= 2019:
    print(0)
    exit()
else:
    start = L % 2019
    end = R % 2019
    candidate = []
    for i in range(start, end + 1):
        candidate.append(i % 2019)
    candidate.sort()
    ans = []
    for i in range(len(candidate)):
        for j in range(len(candidate)):
            if i == j:
                continue
            else:
                ans.append((candidate[i] * candidate[j]) % 2019)
    ans.sort()
    print(ans[0])


### FIXED CODE ###

L, R = map(int, input().split())

tmp = R - L + 1
if tmp >= 2019:
    print(0)
    exit()
else:
    start = L % 2019
    end = R % 2019
    candidate = []
    for i in range(start, end + 1):
        candidate.append(i % 2019)
    candidate.sort()
    ans = []
    for i in range(len(candidate)):
        if i == (len(candidate) - 1):
            continue
        for j in range(i + 1, len(candidate)):
            if i == j:
                continue
            else:
                ans.append((candidate[i] * candidate[j]) % 2019)
    ans.sort()
    print(ans[0])