'''
F(n) = 7 − n при n < 7;
F(n) = 2 · (n − 3) · F(n − 3); если n ⩾ 7 и делится на 3;
F(n) = 2 · (F(n − 1) + F(n − 2)) − 10 · n; если n ⩾ 7 и не делится на 3:
(F(30) − F(25))/6

В ответе запишите четыре последние цифры
полученного значения.
'''


def F(n):
    if n < 7:
        return 7 - n
    if n % 3 == 0:
        return 2 * (n - 3) * F(n - 3)
    return 2 * (F(n - 1) + F(n - 2)) - 10 * n
    
res = (F(30) - F(25))//6
print(res % 10000) # 1273 ok