import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Euler266 {

    static List<Integer> primesBelow(int limit) {
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int p = 2; p * p < limit; p++) {
            if (isPrime[p]) {
                for (int q = p * p; q < limit; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int p = 2; p < limit; p++) {
            if (isPrime[p])
                primes.add(p);
        }
        return primes;
    }

    static class Subset implements Comparable<Subset> {
        double logValue;
        int mask;

        Subset(double logValue, int mask) {
            this.logValue = logValue;
            this.mask = mask;
        }

        @Override
        public int compareTo(Subset other) {
            return Double.compare(this.logValue, other.logValue);
        }
    }

    static Subset[] enumerateSubsets(List<Integer> primes) {
        int n = primes.size();
        int m = 1 << n;
        double[] logs = new double[n];
        for (int i = 0; i < n; i++) {
            logs[i] = Math.log(primes.get(i));
        }

        Subset[] out = new Subset[m];
        out[0] = new Subset(0.0, 0);
        for (int mask = 1; mask < m; mask++) {
            int lsb = mask & (-mask);
            int bit = Integer.numberOfTrailingZeros(lsb);
            int prev = mask ^ lsb;
            out[mask] = new Subset(out[prev].logValue + logs[bit], mask);
        }
        Arrays.sort(out);
        return out;
    }

    static BigInteger buildFromMasks(List<Integer> leftPrimes, List<Integer> rightPrimes, int leftMask, int rightMask) {
        BigInteger v = BigInteger.ONE;
        int lm = leftMask;
        while (lm != 0) {
            int b = Integer.numberOfTrailingZeros(lm);
            v = v.multiply(BigInteger.valueOf(leftPrimes.get(b)));
            lm &= (lm - 1);
        }
        int rm = rightMask;
        while (rm != 0) {
            int b = Integer.numberOfTrailingZeros(rm);
            v = v.multiply(BigInteger.valueOf(rightPrimes.get(b)));
            rm &= (rm - 1);
        }
        return v;
    }

    static BigInteger solveForPrimes(List<Integer> primes) {
        BigInteger productAll = BigInteger.ONE;
        double totalLog = 0.0;
        for (int p : primes) {
            productAll = productAll.multiply(BigInteger.valueOf(p));
            totalLog += Math.log(p);
        }
        double targetLog = totalLog * 0.5;

        int split = primes.size() / 2;
        List<Integer> leftPrimes = new ArrayList<>(primes.subList(0, split));
        List<Integer> rightPrimes = new ArrayList<>(primes.subList(split, primes.size()));

        Subset[] left = enumerateSubsets(leftPrimes);
        Subset[] right = enumerateSubsets(rightPrimes);

        double bestLog = -1.0;
        int j = right.length - 1;
        for (Subset l : left) {
            while (j > 0 && l.logValue + right[j].logValue > targetLog + 1e-12)
                j--;
            double cand = l.logValue + right[j].logValue;
            if (cand <= targetLog + 1e-12 && cand > bestLog) {
                bestLog = cand;
            }
        }

        BigInteger bestValue = BigInteger.ZERO;
        j = right.length - 1;
        for (Subset l : left) {
            while (j > 0 && l.logValue + right[j].logValue > targetLog + 1e-10)
                j--;

            for (int t = -1; t <= 12; t++) {
                int k = j - t;
                if (k < 0 || k >= right.length)
                    continue;

                Subset r = right[k];
                double candLog = l.logValue + r.logValue;
                if (t >= 0 && candLog + 1e-9 < bestLog)
                    break;
                if (candLog > targetLog + 1e-8)
                    continue;

                BigInteger cand = buildFromMasks(leftPrimes, rightPrimes, l.mask, r.mask);
                if (cand.multiply(cand).compareTo(productAll) <= 0 && cand.compareTo(bestValue) > 0) {
                    bestValue = cand;
                }
            }
        }
        return bestValue;
    }

    public static void main(String[] args) {
        List<Integer> primes = primesBelow(190);
        BigInteger ans = solveForPrimes(primes);
        System.out.println(ans.remainder(new BigInteger("10000000000000000")).toString());
    }
}