import java.math.BigInteger;

public class Euler188 {
    static long eulerPhi(long n) {
        long r = n;
        for (long p = 2; p * p <= n; p++) {
            if (n % p != 0)
                continue;
            while (n % p == 0)
                n /= p;
            r -= r / p;
        }
        if (n > 1)
            r -= r / n;
        return r;
    }

    static long tetMod(long b, int h, long m) {
        if (m == 1)
            return 0;
        if (h == 1)
            return b % m;
        long ph = eulerPhi(m), exp = tetMod(b, h - 1, ph);
        if (gcd(b, m) != 1)
            exp += ph;
        return BigInteger.valueOf(b).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(m)).longValue();
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(tetMod(1777, 1855, 100000000L));
    }
}