from functools import *

# гра­нич­ное зна­че­ние

a = list(map(int, str(2**63-1)))

@cache

def f(s, l, fl):

# если по­сле­до­ва­тель­ность нуж­ной длины, про­ве­ря­ем, что сумма нам под­хо­дит,

# и вы­хо­дим из ре­кур­сии.

if l == 0: return s == 159

# про­ве­ря­ем огра­ни­чен­ные под­по­сле­до­ва­тель­но­сти боль­шей длины

return sum(f(s+x, l-1, fl and (x == a[-l])) for x in range([10, a[-l]+1][fl]))

# ответ - ко­ли­че­ство огра­ни­чен­ных по­сле­до­ва­тель­но­стей не­об­хо­ди­мой длины

print(f(0, len(a), 1))

from functools import *

def f(n, b):

# гра­нич­ное зна­че­ние в b-ичной сс

a = []

while n > 0:

a = [n % b] + a

n //= b

@cache

def g(s, l, fl):

# если по­сле­до­ва­тель­ность нуж­ной длины, про­ве­ря­ем, что сумма нам под­хо­дит,

# и вы­хо­дим из ре­кур­сии.

if l == 0: return s == 121

# про­ве­ря­ем огра­ни­чен­ные под­по­сле­до­ва­тель­но­сти боль­шей длины

return sum(g(s+x, l-1, fl and (x == a[-l])) for x in range([b, a[-l]+1][fl]))

return g(0, len(a), 1)

# ответ - раз­ность между ко­ли­че­ством под­хо­дя­щих чисел на от­рез­ке [1; 5*6^20] и по­лу­ин­тер­ва­ле [1; 4*6^20).

print(f(5*6**20, 9) - f(4*6**20-1, 9))