public class Euler900 {
    static final long MOD = 900497239L;

    static long modMul(long a, long b) {
        return (a * b) % MOD;
    }

    static long modPow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = modMul(result, base);
            }
            base = modMul(base, base);
            exp >>= 1;
        }
        return result;
    }

    static long modInv(long a) {
        return modPow(a, MOD - 2);
    }

    static long computeSClosed(long N) {
        long inv3 = modInv(3);
        long inv7 = modInv(7);

        long pow4N = modPow(4, N);
        long sumA = modMul((pow4N - 1 + MOD) % MOD, inv3);

        long sumC = (modPow(2, N + 1) - 2) % MOD;
        if (sumC < 0)
            sumC += MOD;

        long K = N / 2;
        long pow8K = modPow(8, K);
        long geo = modMul((pow8K - 1 + MOD) % MOD, inv7);
        long sumB = modMul(3, geo);
        if (N % 2 == 1) {
            sumB += pow8K;
            if (sumB >= MOD)
                sumB -= MOD;
        }

        long ans = (sumA + sumB - sumC) % MOD;
        if (ans < 0)
            ans += MOD;
        return ans;
    }

    public static String solve() {
        return Long.toString(computeSClosed(10000));
    }

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