import java.math.BigInteger;

public class Euler312 {
    static long pow_u64(long base, int exp) {
        long result = 1;
        while (exp-- > 0)
            result *= base;
        return result;
    }

    static long mul_mod(long a, long b, long mod) {
        return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
    }

    static long pow_mod(long base, long exp, long mod) {
        if (mod == 1)
            return 0;
        return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).longValue();
    }

    static long inverse_mod(long a, long mod) {
        a %= mod;
        long phi = mod - mod / 13;
        return pow_mod(a, phi - 1, mod);
    }

    static long crt_coprime(long a1, long m1, long a2, long m2) {
        long inv_m1 = inverse_mod(m1 % m2, m2);
        long delta = (a2 >= a1 % m2) ? (a2 - (a1 % m2)) : (a2 + m2 - (a1 % m2));
        long t = mul_mod(delta, inv_m1, m2);
        return a1 + m1 * t;
    }

    static long c_mod_13_power_from_n_residue(long n_residue, boolean n_is_large, int k) {
        long mod = pow_u64(13, k);

        if (!n_is_large && n_residue <= 2) {
            return 1 % mod;
        }

        long ord12 = 2 * pow_u64(13, k - 1);
        long two_ord = 2 * ord12;
        long lambda_val = (k >= 2) ? (12 * pow_u64(13, k - 2)) : 2;

        long exp = (n_residue + lambda_val - 2) % lambda_val;
        long x = pow_mod(3, exp, two_ord);

        long numer = (x + two_ord - 3) % two_ord;
        long e = (numer / 2) % ord12;

        return mul_mod(8 % mod, pow_mod(12, e, mod), mod);
    }

    public static String solve() {
        long n0 = 10000;

        long a_mod_13_4 = c_mod_13_power_from_n_residue(n0, false, 4);
        long a_mod_12x13_4 = crt_coprime(0, 12, a_mod_13_4, pow_u64(13, 4));

        long b_mod_13_6 = c_mod_13_power_from_n_residue(a_mod_12x13_4, true, 6);
        long b_mod_12x13_6 = crt_coprime(0, 12, b_mod_13_6, pow_u64(13, 6));

        long result = c_mod_13_power_from_n_residue(b_mod_12x13_6, true, 8);
        return String.valueOf(result);
    }

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