№23 — #23149

from functools import lru_cache
@lru_cache(None)
def f(n, last='', streak=0, dcount=0, has15=False, has33=False):
    if n == 72:
        return 1 if (has15 or has33) and dcount == 1 else 0
    if n > 72:
        return 0
ans = 0
ns = streak + 1 if last == 'A' else 1
    if ns <= 2:
        ans += f(n + 1, 'A', ns, dcount, has15 or n + 1 == 15, has33 or n + 1 == 33)
ans += f(n + 6, 'B', 1, dcount, has15 or n + 6 == 15, has33 or n + 6 == 33)
    ans += f(n * 2, 'C', 1, dcount, has15 or n * 2 == 15, has33 or n * 2 == 33)
x = n * n
    if x <= 72 and dcount < 1:
        ans += f(x, 'D', 1, dcount + 1, has15 or x == 15, has33 or x == 33)
x = n + max(map(int, str(n)))
    if x <= 72:
        ans += f(x, 'E', 1, dcount, has15 or x == 15, has33 or x == 33)
return ans
raw = f(4)
print(raw % 89)