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

public class Euler500 {

    static class HeapNode implements Comparable<HeapNode> {
        double logValue;
        long modValue;

        HeapNode(double logValue, long modValue) {
            this.logValue = logValue;
            this.modValue = modValue;
        }

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

    private static int nthPrimeUpperBound(int n) {
        if (n < 6)
            return 20;
        double x = n;
        double estimate = x * (Math.log(x) + Math.log(Math.log(x))) + 10.0;
        return (int) estimate + 100;
    }

    private static List<Integer> firstNPrimes(int n) {
        int limit = nthPrimeUpperBound(n);
        while (true) {
            boolean[] isComposite = new boolean[limit + 1];
            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= limit; ++i) {
                if (!isComposite[i]) {
                    primes.add(i);
                    if ((long) i * i <= limit) {
                        for (int j = i * i; j <= limit; j += i) {
                            isComposite[j] = true;
                        }
                    }
                }
            }
            if (primes.size() >= n) {
                return primes.subList(0, n);
            }
            limit *= 2;
        }
    }

    public static void main(String[] args) {
        int power = 500500;
        long mod = 500500507L;

        List<Integer> primes = firstNPrimes(power);
        PriorityQueue<HeapNode> heap = new PriorityQueue<>();

        for (int p : primes) {
            heap.add(new HeapNode(Math.log(p), p % mod));
        }

        long ans = 1L;
        for (int step = 0; step < power; ++step) {
            HeapNode cur = heap.poll();
            ans = (ans * cur.modValue) % mod;
            long squaredMod = (cur.modValue * cur.modValue) % mod;
            heap.add(new HeapNode(cur.logValue * 2.0, squaredMod));
        }

        System.out.println(ans);
    }
}