public class Euler649 {
    static final long kMod = 1000000000L;

    static long modPow(long a, long e) {
        long r = 1 % kMod;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * a) % kMod;
            a = (a * a) % kMod;
            e >>= 1;
        }
        return r;
    }

    public static String solve() {
        int n = 10000019;
        int c = 100;

        long[] cnt = new long[8];
        int[] buf = new int[8];
        int[] moves = { 2, 3, 5, 7 };

        for (int i = 0; i < n; ++i) {
            int g = 0;
            if (i >= 2) {
                boolean[] seen = new boolean[6];
                for (int d : moves) {
                    if (i >= d)
                        seen[buf[(i - d) & 7]] = true;
                }
                while (g < 6 && seen[g])
                    ++g;
            }
            buf[i & 7] = g;
            cnt[g]++;
        }

        long[] cnt2 = new long[8];
        for (int a = 0; a < 8; ++a) {
            if (cnt[a] == 0)
                continue;
            for (int b = 0; b < 8; ++b) {
                if (cnt[b] == 0)
                    continue;
                cnt2[a ^ b] += cnt[a] * cnt[b];
            }
        }

        long[] cnt2m = new long[8];
        for (int i = 0; i < 8; ++i)
            cnt2m[i] = cnt2[i] % kMod;

        long[] dp = new long[8];
        long[] ndp = new long[8];
        dp[0] = 1;

        for (int t = 0; t < c; ++t) {
            for (int i = 0; i < 8; i++)
                ndp[i] = 0;
            for (int x = 0; x < 8; ++x) {
                long vx = dp[x];
                if (vx == 0)
                    continue;
                for (int g = 0; g < 8; ++g) {
                    ndp[x ^ g] = (ndp[x ^ g] + vx * cnt2m[g]) % kMod;
                }
            }
            System.arraycopy(ndp, 0, dp, 0, 8);
        }

        long n2m = ((long) (n % kMod) * (long) (n % kMod)) % kMod;
        long total = modPow(n2m, c);
        long ans = (total + kMod - dp[0]) % kMod;

        return String.format("%09d", ans);
    }

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