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

public class Euler952 {

    static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }

    static int vPFactorial(int n, int p) {
        int e = 0;
        while (n > 0) {
            n /= p;
            e += n;
        }
        return e;
    }

    static int v2Int(long x) {
        int v = 0;
        while ((x & 1) == 0) {
            x >>= 1;
            ++v;
        }
        return v;
    }

    static class SpfResult {
        int[] spf;
        List<Integer> primes;

        SpfResult(int[] spf, List<Integer> primes) {
            this.spf = spf;
            this.primes = primes;
        }
    }

    static SpfResult buildSpfAndPrimes(int n) {
        int[] spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>(n / 10);

        for (int i = 2; i <= n; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long v = (long) p * i;
                if (v > n || p > spf[i]) {
                    break;
                }
                spf[(int) v] = p;
            }
        }
        return new SpfResult(spf, primes);
    }

    static class Factor {
        int p;
        int e;

        Factor(int p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static List<Factor> factorizeInt(int x, int[] spf) {
        List<Factor> fac = new ArrayList<>();
        while (x > 1) {
            int p = spf[x];
            int e = 0;
            do {
                x /= p;
                ++e;
            } while (x > 1 && spf[x] == p);
            fac.add(new Factor(p, e));
        }
        return fac;
    }

    static long computeRMod(long p, int n, long outMod) {
        SpfResult res = buildSpfAndPrimes(n);
        int[] spf = res.spf;
        List<Integer> primes = res.primes;
        int[] maxExp = new int[n + 1];

        for (int q : primes) {
            if (q > n) {
                break;
            }

            int e = vPFactorial(n, q);

            if (q == 2) {
                int exp2 = 0;
                if (e >= 2) {
                    if ((p & 3) == 1) {
                        int u = v2Int(p - 1);
                        exp2 = (e <= u) ? 0 : (e - u);
                    } else {
                        int v = v2Int(p + 1);
                        exp2 = (e <= v) ? 1 : (e - v);
                    }
                }
                if (exp2 > maxExp[2]) {
                    maxExp[2] = exp2;
                }
                continue;
            }

            long t = q - 1;
            List<Factor> facQm1 = factorizeInt(q - 1, spf);
            long baseQ = p % q;

            for (Factor f : facQm1) {
                for (int i = 0; i < f.e; ++i) {
                    if (t % f.p == 0 && modPow(baseQ, t / f.p, q) == 1) {
                        t /= f.p;
                    } else {
                        break;
                    }
                }
            }

            long tmp = t;
            for (Factor f : facQm1) {
                int cnt = 0;
                while (tmp % f.p == 0) {
                    tmp /= f.p;
                    ++cnt;
                }
                if (cnt > maxExp[f.p]) {
                    maxExp[f.p] = cnt;
                }
            }

            int s = 1;
            if (e > 1) {
                long modQ2 = (long) q * q;
                if (modPow(p % modQ2, t, modQ2) == 1) {
                    s = 2;
                    if (e > 2) {
                        BigInteger base = BigInteger.valueOf(p);
                        BigInteger exp = BigInteger.valueOf(t);
                        BigInteger mod = BigInteger.valueOf(q).pow(3);
                        BigInteger bigQ = BigInteger.valueOf(q);
                        for (int k = 3; k <= e; ++k) {
                            if (base.modPow(exp, mod).equals(BigInteger.ONE)) {
                                s = k;
                                mod = mod.multiply(bigQ);
                            } else {
                                break;
                            }
                        }
                    }
                }
            }

            int extra = e - s;
            if (extra > maxExp[q]) {
                maxExp[q] = extra;
            }
        }

        long ans = 1 % outMod;
        for (int r = 2; r <= n; ++r) {
            if (maxExp[r] > 0) {
                ans = (ans * modPow(r, maxExp[r], outMod)) % outMod;
            }
        }

        return ans;
    }

    public static String solve() {
        return Long.toString(computeRMod(1000000007L, 10000000, 1000000007L));
    }

    public static void main(String[] args) {
        if (computeRMod(7L, 4, 1000000007L) != 2L || computeRMod(1000000007L, 12, 1000000007L) != 17280L) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}