Рекурсия

Работает на всё. @lru_cache(None) меняем на 100 или 500 если не работает.

Python

import sys
sys.setrecursionlimit(1000000)

from functools import *
@lru_cache(None)  # None меняем на 100 или 500 если не работает

def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

for i in range(14000):  # число ближайшее вперед к числам в задаче
    f(i)

print((f(13766) - 9 * f(13762)) // f(13758))  # Всегда // (целое деление)

Способ 2

# Способ 3 — список (самый быстрый)
f = [0] * 14000
for n in range(len(f)):
    if n < 5:
        f[n] = n
    if n >= 5:
        f[n] = 2 * n * f[n - 4]
print((f[13766] - 9*f[13762]) // f[13758])

📚 Теория

Рекуррентные соотношения. @lru_cache для мемоизации. Всегда // для деления.