import java.util.*;

public class Euler335 {

    static final long EXPONENT_LIMIT = 1000000000000000000L;
    static final long MODULUS = 40353607L;

    static long mulMod(long a, long b, long mod) {
        return (a * b) % mod;
    }

    static long powMod(long base, long exp, long mod) {
        long out = 1L % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                out = mulMod(out, base, mod);
            base = mulMod(base, base, mod);
            exp >>= 1;
        }
        return out;
    }

    static long modInverse(long a, long mod) {
        return java.math.BigInteger.valueOf(a).modInverse(java.math.BigInteger.valueOf(mod)).longValue();
    }

    public static String solve() {
        long inv2 = modInverse(2, MODULUS);
        long inv3 = modInverse(3, MODULUS);

        long p2 = powMod(2, EXPONENT_LIMIT + 1, MODULUS);
        long p3 = powMod(3, EXPONENT_LIMIT + 1, MODULUS);
        long p4 = powMod(4, EXPONENT_LIMIT + 1, MODULUS);

        long sum_2 = mulMod(2, (p2 + MODULUS - 1) % MODULUS, MODULUS);
        long sum_4 = mulMod((p4 + MODULUS - 1) % MODULUS, inv3, MODULUS);
        long sum_3 = mulMod((p3 + MODULUS - 1) % MODULUS, inv2, MODULUS);

        long ans = (sum_2 + sum_4 + MODULUS - sum_3) % MODULUS;
        return String.valueOf(ans);
    }

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