Задание №75434 ЕГЭ Информатике

from functools import *
 
def f(n, 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)
 
print(f(5*6**20, 9) - f(4*6**20-1, 9))