import java.util.ArrayList;
import java.util.List;

public class Euler533 {

    private static final long kLast = 1000000000L;

    private static long powMod(long a, int e, long mod) {
        long r = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1) != 0) {
                r = (r * a) % mod;
            }
            a = (a * a) % mod;
            e >>= 1;
        }
        return r;
    }

    private static byte[] sieveIsPrime(int n) {
        byte[] isPrime = new byte[n + 1];
        for (int i = 0; i <= n; i++)
            isPrime[i] = 1;
        if (n >= 0)
            isPrime[0] = 0;
        if (n >= 1)
            isPrime[1] = 0;
        for (int p = 2; (long) p * p <= n; ++p) {
            if (isPrime[p] == 1) {
                for (int m = p * p; m <= n; m += p) {
                    isPrime[m] = 0;
                }
            }
        }
        return isPrime;
    }

    static class BestState {
        double logValue = -1e300;
        long modValue = 0;
        long L = 0;
    }

    static class Pair {
        long p;
        int e;

        Pair(long p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    private static long exponentInFactorization(List<Pair> fac, long p) {
        for (Pair pair : fac) {
            if (pair.p == p)
                return pair.e;
        }
        return 0;
    }

    private static void evaluateL(long M, byte[] isPrime, long L, List<Pair> fac, BestState best) {
        long[] divisors = new long[8192];
        divisors[0] = 1;
        int size = 1;

        for (Pair pair : fac) {
            int cur = size;
            long pe = 1;
            for (int i = 1; i <= pair.e; ++i) {
                pe *= pair.p;
                for (int j = 0; j < cur; ++j) {
                    divisors[size++] = divisors[j] * pe;
                }
            }
        }

        long v2 = exponentInFactorization(fac, 2);
        int exp2 = (v2 == 0) ? 1 : (int) (v2 + 2);

        double logN = exp2 * Math.log(2.0);
        long modN = powMod(2, exp2, kLast);

        for (int i = 0; i < size; ++i) {
            long p = divisors[i] + 1;
            if (p == 2)
                continue;
            if (p > M + 1)
                continue;
            if (isPrime[(int) p] == 0)
                continue;

            int exp = (int) exponentInFactorization(fac, p) + 1;
            logN += exp * Math.log(p);
            modN = (modN * powMod(p, exp, kLast)) % kLast;
        }

        if (logN > best.logValue) {
            best.logValue = logN;
            best.modValue = modN;
            best.L = L;
        }
    }

    private static void dfsGenerate(long[] primes, long M, byte[] isPrime, int idx, int maxExp,
            long cur, List<Pair> fac, BestState best) {
        evaluateL(M, isPrime, cur, fac, best);
        if (idx >= primes.length)
            return;

        long p = primes[idx];
        long val = cur;
        for (int e = 1; e <= maxExp; ++e) {
            if (val > M / p)
                break;
            val *= p;
            fac.add(new Pair(p, e));
            dfsGenerate(primes, M, isPrime, idx + 1, e, val, fac, best);
            fac.remove(fac.size() - 1);
        }
    }

    private static long solveLast9(long boundMinus1) {
        long M = boundMinus1;
        byte[] isPrime = sieveIsPrime((int) (M + 1));
        long[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 };

        BestState best = new BestState();
        List<Pair> fac = new ArrayList<>();
        dfsGenerate(primes, M, isPrime, 0, 60, 1, fac, best);

        return (best.modValue + 1) % kLast;
    }

    public static void main(String[] args) {
        long last9 = solveLast9(20000000L - 1);
        System.out.printf("%09d\n", last9);
    }
}