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

public class Euler615 {
    static final long TARGET_COUNT = 1000000L;
    static final long MOD = 123454321L;
    static final int PRIME_LIMIT = 1000000;

    static List<Integer> sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;
        for (int i = 2; (long) i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    static class Enumerator {
        List<Integer> primes;
        double[] logPrimes;
        long needFactors;
        long limitN;
        double logLimitN;
        List<Long> values;

        Enumerator(List<Integer> primes, double[] logPrimes, long needFactors, long limitN) {
            this.primes = primes;
            this.logPrimes = logPrimes;
            this.needFactors = needFactors;
            this.limitN = limitN;
            this.logLimitN = Math.log(limitN);
            this.values = new ArrayList<>();
        }

        boolean dfs(int i, long used, long n) {
            if (i >= primes.size())
                return false;
            if (used < needFactors) {
                double lb = Math.log(n) + (needFactors - used) * logPrimes[i];
                if (lb > logLimitN + 1e-12)
                    return false;
            }
            if (used >= needFactors) {
                values.add(n);
            }

            int j = i;
            while (j < primes.size()) {
                long p = primes.get(j);
                if ((long) n * p > limitN || (long) n * p < 0)
                    break; // overflow check
                if (!dfs(j, used + 1, n * p))
                    break;
                j++;
            }
            return true;
        }
    }

    public static String solve() {
        List<Integer> primes = sievePrimes(PRIME_LIMIT);
        double[] logPrimes = new double[primes.size()];
        for (int i = 0; i < primes.size(); i++) {
            logPrimes[i] = Math.log(primes.get(i));
        }

        long c = 1;
        long nLimit = 3;
        List<Long> values = new ArrayList<>();

        while (true) {
            Enumerator e = new Enumerator(primes, logPrimes, c, nLimit);
            e.dfs(0, 0, 1);
            values = e.values;
            if (values.size() >= TARGET_COUNT)
                break;
            c++;
            nLimit *= 3;
        }

        Collections.sort(values);
        long x = values.get((int) (TARGET_COUNT - 1));

        for (long t = c; t < TARGET_COUNT; t++) {
            x = (x * 2) % MOD;
        }

        return Long.toString(x);
    }

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