public class Euler160 {
    static final long M2 = 3125, PHI = 2500;
    static long[] P = new long[(int) M2 + 1];

    static long power(long b, long e, long m) {
        long r = 1;
        b %= m;
        while (e > 0) {
            if (e % 2 == 1)
                r = r * b % m;
            b = b * b % m;
            e /= 2;
        }
        return r;
    }

    static void initP() {
        P[0] = 1;
        for (int i = 1; i <= (int) M2; i++)
            P[i] = i % 5 != 0 ? (P[i - 1] * i) % M2 : P[i - 1];
    }

    static long getPmod(long n) {
        long q = n / M2, r = n % M2;
        return ((q % 2 == 0 ? 1 : M2 - 1) * P[(int) r]) % M2;
    }

    static long factNo5(long n) {
        return n == 0 ? 1 : (getPmod(n) * factNo5(n / 5)) % M2;
    }

    static long count5(long n) {
        long c = 0;
        while (n > 0) {
            c += n / 5;
            n /= 5;
        }
        return c;
    }

    static long crt(long r) {
        long t = (32 - (r % 32)) % 32;
        long k = (t * 29) % 32;
        return r + k * M2;
    }

    static long f(long n) {
        if (n < 10) {
            long r = 1;
            for (int i = 1; i <= n; i++)
                r *= i;
            while (r % 10 == 0)
                r /= 10;
            return r % 100000;
        }
        long fn5 = factNo5(n), n5 = count5(n), inv2 = power(2, PHI - n5 % PHI, M2);
        return crt((fn5 * inv2) % M2);
    }

    public static void main(String[] args) {
        initP();
        System.out.printf("%05d%n", f(1000000000000L));
    }
}