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

from functools import *
 
n = 3 ** 40
a = []
while n > 0:
    a = [n % 15] + a
    n //= 15
 
@cache
def f(p, l, fl, zero):
    if p > 7560: return 0
 
    if l == 0: return p == 7560
 
    return sum(f(p * (max(x, 1) if zero else x), l - 1, fl and (x == a[-l]), zero and (x == 0)) for x in range([15, a[-l] + 1][fl]))
 
 
print(f(1, len(a), 1, 1))