Роллер

def speed(x, n, mod):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return (speed(x, n // 2, mod) ** 2) % mod
    return (speed(x, n - 1, mod) * x) % mod 
        
f = 5**.5
a1 = (1 + f)/2
a2 = (f - 1)/2
n = 11258999000000
#n = int(input())
n = (n-1)*3 + 5
k = 999999937
an = (speed(a1,n,k) - speed(a2,n,k))/f
print(round(an))

def dot(m1, m2, p):
#умножение матрицы m1 на m2 в Z_p
    return [
        [sum(x * y for x, y in zip(m1_row, m2_col)) % p for m2_col in zip(*m2)] for m1_row in m1
    ]
 
def get_one(n):
#возвращает единичную матрицу n x n
    return [[1 if i==j else 0 for j in range(n)] for i in range(n)]
 
def mod_exp(m, b, p):
#быстроу возведение матрицы m в степень b в Z_p
    if b == 0:
        return get_one(len(m[0])) 
    if b % 2 == 1:
        return dot(m, mod_exp(m, b-1, p), p) 
    m_2 = mod_exp(m, b/2, p)
    return dot(m_2, m_2, p)
 
p = 999999937
step = [[3, 2, 2], [1, 1, 1], [1, 0, 0]]
n = 11258999000000
#n = int(input())
print( sum( row[0] for row in mod_exp(step, n, p) ) % p )

def foo(n):
    if n == 0:
        return (0, 1)
    a, b = foo(n // 2)
    if n % 2:
        return ((a * a + b * b) % m, (2 * a * b + b * b) % m)
    return ((2 * a * b - a * a) % m, (a * a + b * b) % m)
 
 
n = 11258999000000
m = 999999937
print(foo(3 * n + 2)[0])