import numpy as np

a = 2
b = 3
vs = [2, 2 * a]
for i in range(2, 10):
    vs.append(2 * a * vs[i - 1] + (b - a**2) * vs[i - 2])
print(vs)

# def mod_pow(base, exponent, modulus):
#     result = 1
#     base = base % modulus
#     while exponent > 0:
#         if exponent % 2 == 1:
#             result = (result * base) % modulus
#         exponent //= 2
#         base = (base * base) % modulus
#     return result
# MOD = 10**9 + 7

def solve(a, b, k):
    u, v, w, x = 2 * a, b - a**2, 1, 0
    r1, r2, r3, r4 = 1, 0, 0, 1
    while k > 0:
        if k % 2:
            r1, r2, r3, r4 = (r1 * u + r2 * w) % MOD, (r1 * v + r2 * x) % MOD, (r3 * u + r4 * w) % MOD, (r3 * v + r4 * x) % MOD
        k //= 2
        u, v, w, x = (u * u + v * w) % MOD, (v * (u + x))% MOD, (w * (u + x)) % MOD, (x**2 + v * w) % MOD
    return ((2 * a) * r3 + 2 * r4) % MOD

r = solve(2, 3, 10**6)
print(r)