public class Euler382 {
    private static final long kMod = 1000000000L;
    private static final int kOrder = 8;
    private static final long[] kRecurrence = { 3, -2, 2, -5, 1, 1, 3, -2 };
    private static final long[] kBase = { 1, 2, 4, 6, 11, 20, 36, 67 };

    private static long[][] matMul(long[][] a, long[][] b) {
        long[][] c = new long[9][9];
        for (int i = 0; i < 9; ++i) {
            for (int k = 0; k < 9; ++k) {
                if (a[i][k] == 0)
                    continue;
                for (int j = 0; j < 9; ++j) {
                    if (b[k][j] == 0)
                        continue;
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % kMod;
                }
            }
        }
        return c;
    }

    private static long modNorm(long val) {
        long x = val % kMod;
        if (x < 0)
            x += kMod;
        return x;
    }

    private static long[] applyMatPow(long[][] base, long exp, long[] vec) {
        long[][] acc = new long[9][9];
        for (int i = 0; i < 9; ++i)
            acc[i][i] = 1;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                acc = matMul(base, acc);
            }
            base = matMul(base, base);
            exp >>= 1;
        }

        long[] out = new long[9];
        for (int i = 0; i < 9; ++i) {
            long s = 0;
            for (int j = 0; j < 9; ++j) {
                s = (s + acc[i][j] * vec[j]) % kMod;
            }
            out[i] = s;
        }
        return out;
    }

    private static long powMod(long base, long exp) {
        long res = 1;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * base) % kMod;
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return res;
    }

    public static String solve() {
        long n = 1000000000000000000L;
        long s8 = 0;
        for (long v : kBase) {
            s8 = (s8 + v) % kMod;
        }

        long[] state = {
                kBase[7] % kMod, kBase[6] % kMod, kBase[5] % kMod, kBase[4] % kMod,
                kBase[3] % kMod, kBase[2] % kMod, kBase[1] % kMod, kBase[0] % kMod, s8
        };

        long[][] trans = new long[9][9];
        for (int j = 0; j < kOrder; ++j) {
            trans[0][j] = modNorm(kRecurrence[j]);
        }
        for (int r = 1; r < kOrder; ++r) {
            trans[r][r - 1] = 1;
        }
        for (int j = 0; j < kOrder; ++j) {
            trans[8][j] = modNorm(kRecurrence[j]);
        }
        trans[8][8] = 1;

        long[] advanced = applyMatPow(trans, n - 8, state);
        long sumB = advanced[8];

        long pow2 = powMod(2, n);
        long ans = modNorm(pow2 - 1 - sumB);
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}