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

public class Euler1005 {
    private static final int DEFAULT_TARGET = 2026;
    private static final long MOD = 1_000_000_000L;

    private static final class Options {
        int target = DEFAULT_TARGET;
        boolean runCheckpoints = true;
    }

    private static final class PrimeDp {
        int target;
        List<Integer> primes;
        BigInteger[][] suffixCount;
    }

    private static List<Integer> primesUpTo(int limit) {
        List<Integer> primes = new ArrayList<>();
        if (limit < 2) {
            return primes;
        }

        boolean[] composite = new boolean[limit + 1];
        for (int p = 2; p * p <= limit; ++p) {
            if (!composite[p]) {
                for (int multiple = p * p; multiple <= limit; multiple += p) {
                    composite[multiple] = true;
                }
            }
        }

        for (int value = 2; value <= limit; ++value) {
            if (!composite[value]) {
                primes.add(value);
            }
        }
        return primes;
    }

    private static PrimeDp buildDp(int target) {
        PrimeDp dp = new PrimeDp();
        dp.target = target;
        dp.primes = primesUpTo(target);
        int count = dp.primes.size();
        dp.suffixCount = new BigInteger[count + 1][target + 1];
        for (int i = 0; i <= count; ++i) {
            Arrays.fill(dp.suffixCount[i], BigInteger.ZERO);
        }
        dp.suffixCount[count][0] = BigInteger.ONE;

        for (int i = count - 1; i >= 0; --i) {
            int prime = dp.primes.get(i);
            for (int sum = 0; sum <= target; ++sum) {
                BigInteger ways = dp.suffixCount[i + 1][sum];
                if (sum >= prime) {
                    ways = ways.add(dp.suffixCount[i + 1][sum - prime]);
                }
                dp.suffixCount[i][sum] = ways;
            }
        }

        return dp;
    }

    private static List<Integer> kthPrimeList(PrimeDp dp, BigInteger rank) {
        BigInteger total = dp.suffixCount[0][dp.target];
        if (rank.compareTo(BigInteger.ZERO) <= 0 || rank.compareTo(total) > 0) {
            throw new IllegalArgumentException("requested rank is outside the available prime lists");
        }

        int remaining = dp.target;
        int start = 0;
        List<Integer> result = new ArrayList<>();

        while (remaining > 0) {
            boolean found = false;
            for (int i = start; i < dp.primes.size(); ++i) {
                int prime = dp.primes.get(i);
                if (prime > remaining) {
                    break;
                }

                BigInteger block = dp.suffixCount[i + 1][remaining - prime];
                if (rank.compareTo(block) > 0) {
                    rank = rank.subtract(block);
                    continue;
                }

                result.add(prime);
                remaining -= prime;
                start = i + 1;
                found = true;
                break;
            }

            if (!found) {
                throw new IllegalStateException("could not unrank the requested prime list");
            }
        }

        return result;
    }

    private static List<Integer> medianPrimeList(PrimeDp dp) {
        BigInteger total = dp.suffixCount[0][dp.target];
        if (total.equals(BigInteger.ZERO)) {
            throw new IllegalArgumentException("there is no prime list for the requested target");
        }
        return kthPrimeList(dp, total.add(BigInteger.ONE).divide(BigInteger.TWO));
    }

    private static long productMod(List<Integer> values) {
        long product = 1;
        for (int value : values) {
            product = product * value % MOD;
        }
        return product;
    }

    private static void enumerateBruteforce(
            List<Integer> primes,
            int start,
            int remaining,
            List<Integer> current,
            List<List<Integer>> lists) {
        if (remaining == 0) {
            lists.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < primes.size(); ++i) {
            int prime = primes.get(i);
            if (prime > remaining) {
                break;
            }
            current.add(prime);
            enumerateBruteforce(primes, i + 1, remaining - prime, current, lists);
            current.remove(current.size() - 1);
        }
    }

    private static List<List<Integer>> bruteLists(int target) {
        List<List<Integer>> lists = new ArrayList<>();
        enumerateBruteforce(primesUpTo(target), 0, target, new ArrayList<>(), lists);
        return lists;
    }

    private static void requireCheckpoint(boolean ok, String message) {
        if (!ok) {
            throw new AssertionError("checkpoint failed: " + message);
        }
    }

    private static void runCheckpoints() {
        PrimeDp dp20 = buildDp(20);
        List<List<Integer>> expected = List.of(
                List.of(2, 5, 13),
                List.of(2, 7, 11),
                List.of(3, 17),
                List.of(7, 13));
        requireCheckpoint(bruteLists(20).equals(expected), "lexicographic lists for 20");
        requireCheckpoint(dp20.suffixCount[0][20].equals(BigInteger.valueOf(4)), "count for 20");
        requireCheckpoint(medianPrimeList(dp20).equals(List.of(2, 7, 11)), "median list for 20");
        requireCheckpoint(productMod(medianPrimeList(dp20)) == 154, "product for 20");

        for (int target = 2; target <= 60; ++target) {
            PrimeDp dp = buildDp(target);
            List<List<Integer>> lists = bruteLists(target);
            requireCheckpoint(dp.suffixCount[0][target].equals(BigInteger.valueOf(lists.size())),
                    "DP count matches brute force for " + target);

            if (!lists.isEmpty()) {
                requireCheckpoint(medianPrimeList(dp).equals(lists.get((lists.size() - 1) / 2)),
                        "median matches brute force for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.ONE).equals(lists.get(0)),
                        "first rank for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.valueOf((lists.size() + 1L) / 2))
                                .equals(lists.get((lists.size() - 1) / 2)),
                        "middle rank for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.valueOf(lists.size())).equals(lists.get(lists.size() - 1)),
                        "last rank for " + target);
            }
        }
    }

    private static Options parseArguments(String[] args) {
        Options options = new Options();
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            if (arg.startsWith("-")) {
                throw new IllegalArgumentException("unknown option: " + arg);
            }
            options.target = Integer.parseInt(arg);
        }

        if (options.target < 0) {
            throw new IllegalArgumentException("target must be nonnegative");
        }
        return options;
    }

    public static void main(String[] args) {
        Options options = parseArguments(args);
        if (options.runCheckpoints) {
            runCheckpoints();
        }

        PrimeDp dp = buildDp(options.target);
        System.out.printf("%09d%n", productMod(medianPrimeList(dp)));
    }
}