MOD = 10**9

# 行列の積 (A * B) % MOD
def mat_mul(A, B):
    n = len(A)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        Ai = A[i]
        for k in range(n):
            aik = Ai[k]
            if aik:
                Bk = B[k]
                for j in range(n):
                    res[i][j] = (res[i][j] + aik * Bk[j]) % MOD
    return res

# 行列の累乗 A^e (mod MOD)
def mat_pow(A, e):
    n = len(A)
    res = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    base = [row[:] for row in A]
    while e > 0:
        if e & 1:
            res = mat_mul(res, base)
        base = mat_mul(base, base)
        e >>= 1
    return res