import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Euler789 {

    static ArrayList<Integer> primesUpto(int n) {
        boolean[] sieve = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            sieve[i] = true;

        for (int i = 2; i * i <= n; i++) {
            if (sieve[i]) {
                for (int j = i * i; j <= n; j += i) {
                    sieve[j] = false;
                }
            }
        }

        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (sieve[i])
                primes.add(i);
        }
        return primes;
    }

    static void enumerateMinCosts(
            ArrayList<Integer> primes, int idx, int cost, long residue,
            int limit, long mod, HashMap<Long, Integer> best) {
        if (idx == primes.size()) {
            Integer currentCost = best.get(residue);
            if (currentCost == null || cost < currentCost) {
                best.put(residue, cost);
            }
            return;
        }

        int q = primes.get(idx);
        int w = q - 1;
        int maxE = (limit - cost) / w;

        long r = residue;
        for (int e = 0; e <= maxE; e++) {
            enumerateMinCosts(primes, idx + 1, cost + e * w, r, limit, mod, best);
            r = (r * q) % mod;
        }
    }

    static boolean findComboExact(
            ArrayList<Integer> primes, int idx, int remCost, long residue,
            long target, long mod, int[] exps) {
        if (idx == primes.size()) {
            return remCost == 0 && residue == target;
        }

        int q = primes.get(idx);
        int w = q - 1;
        int maxE = remCost / w;

        long r = residue;
        for (int e = 0; e <= maxE; e++) {
            exps[idx] = e;
            if (findComboExact(primes, idx + 1, remCost - e * w, r, target, mod, exps)) {
                return true;
            }
            r = (r * q) % mod;
        }

        return false;
    }

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

    static BigInteger solvePrime(long p) {
        int limit = 80;

        while (true) {
            int pmax = (int) Math.min(p - 1, limit + 1);
            ArrayList<Integer> primes = primesUpto(pmax);
            int split = Math.min(4, primes.size());

            ArrayList<Integer> pa = new ArrayList<>(primes.subList(0, split));
            ArrayList<Integer> pb = new ArrayList<>(primes.subList(split, primes.size()));

            HashMap<Long, Integer> bestA = new HashMap<>();
            HashMap<Long, Integer> bestB = new HashMap<>();

            enumerateMinCosts(pa, 0, 0, 1L, limit, p, bestA);
            enumerateMinCosts(pb, 0, 0, 1L, limit, p, bestB);

            long target = p - 1;

            long[] keys = new long[bestA.size()];
            int[] costsA = new int[bestA.size()];
            int idx = 0;
            for (Map.Entry<Long, Integer> entry : bestA.entrySet()) {
                keys[idx] = entry.getKey();
                costsA[idx] = entry.getValue();
                idx++;
            }

            long[] prefix = new long[keys.length + 1];
            prefix[0] = 1;
            for (int i = 0; i < keys.length; i++) {
                prefix[i + 1] = (prefix[i] * keys[i]) % p;
            }

            long invTotal = modPow(prefix[keys.length], p - 2, p);
            long[] invs = new long[keys.length];
            for (int i = keys.length - 1; i >= 0; i--) {
                invs[i] = (invTotal * prefix[i]) % p;
                invTotal = (invTotal * keys[i]) % p;
            }

            int bestTotal = Integer.MAX_VALUE;
            int bestCa = -1, bestCb = -1;
            long bestRa = 0, bestRb = 0;

            for (int i = 0; i < keys.length; i++) {
                long ra = keys[i];
                int ca = costsA[i];
                long need = (target * invs[i]) % p;

                Integer cb = bestB.get(need);
                if (cb == null)
                    continue;

                int total = ca + cb;
                if (total < bestTotal) {
                    bestTotal = total;
                    bestCa = ca;
                    bestCb = cb;
                    bestRa = ra;
                    bestRb = need;
                }
            }

            if (bestTotal != Integer.MAX_VALUE && bestTotal <= limit) {
                int[] expsA = new int[pa.size()];
                int[] expsB = new int[pb.size()];

                boolean okA = findComboExact(pa, 0, bestCa, 1L, bestRa, p, expsA);
                boolean okB = findComboExact(pb, 0, bestCb, 1L, bestRb, p, expsB);

                BigInteger prod = BigInteger.ONE;
                for (int i = 0; i < pa.size(); i++) {
                    BigInteger bq = BigInteger.valueOf(pa.get(i));
                    prod = prod.multiply(bq.pow(expsA[i]));
                }
                for (int i = 0; i < pb.size(); i++) {
                    BigInteger bq = BigInteger.valueOf(pb.get(i));
                    prod = prod.multiply(bq.pow(expsB[i]));
                }

                return prod;
            }

            limit += 40;
            if (limit > 600) {
                throw new RuntimeException("failed to find solution within limit");
            }
        }
    }

    public static String solve() {
        return solvePrime(2000000011L).toString();
    }

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