public class Euler237 {
    static long modNorm(long x, int mod) {
        long v = x % mod;
        if (v < 0) {
            v += mod;
        }
        return v;
    }

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

    static long[] matVecMul(long[][] a, long[] x, int mod) {
        long[] y = new long[4];
        for (int i = 0; i < 4; ++i) {
            long sum = 0;
            for (int j = 0; j < 4; ++j) {
                sum += a[i][j] * x[j];
            }
            y[i] = modNorm(sum, mod);
        }
        return y;
    }

    public static String solve() {
        long n = 1_000_000_000_000L;
        int mod = 100_000_000;

        if (n == 1 || n == 2)
            return String.valueOf(1 % mod);
        if (n == 3)
            return String.valueOf(4 % mod);
        if (n == 4)
            return String.valueOf(8 % mod);

        long[][] step = {
                { 2, 2, modNorm(-2, mod), 1 },
                { 1, 0, 0, 0 },
                { 0, 1, 0, 0 },
                { 0, 0, 1, 0 }
        };

        long[][] acc = {
                { 1, 0, 0, 0 },
                { 0, 1, 0, 0 },
                { 0, 0, 1, 0 },
                { 0, 0, 0, 1 }
        };

        long power = n - 4;
        while (power > 0) {
            if (power % 2 == 1) {
                acc = matMul(acc, step, mod);
            }
            step = matMul(step, step, mod);
            power /= 2;
        }

        long[] base = { 8, 4, 1, 1 };
        long[] out = matVecMul(acc, base, mod);
        return String.valueOf(out[0]);
    }

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