Let's introduce some definitions that will be needed later.

Let prime(x) be the set of prime divisors of x. For example, prime(140) = \{ 2, 5, 7 \}, prime(169) = \{ 13 \}.

Let g(x, p) be the maximum possible integer p^k where k is an integer such that x is divisible by p^k. For example:

  * g(45, 3) = 9 (45 is divisible by 3^2=9 but not divisible by 3^3=27), 
  * g(63, 7) = 7 (63 is divisible by 7^1=7 but not divisible by 7^2=49). 



Let f(x, y) be the product of g(y, p) for all p in prime(x). For example:

  * f(30, 70) = g(70, 2) ⋅ g(70, 3) ⋅ g(70, 5) = 2^1 ⋅ 3^0 ⋅ 5^1 = 10, 
  * f(525, 63) = g(63, 3) ⋅ g(63, 5) ⋅ g(63, 7) = 3^2 ⋅ 5^0 ⋅ 7^1 = 63. 



You have integers x and n. Calculate f(x, 1) ⋅ f(x, 2) ⋅ … ⋅ f(x, n) mod{(10^{9} + 7)}.

Input

The only line contains integers x and n (2 ≤ x ≤ 10^{9}, 1 ≤ n ≤ 10^{18}) — the numbers used in formula.

Output

Print the answer.

Examples

Input


10 2


Output


2


Input


20190929 1605


Output


363165664


Input


947 987654321987654321


Output


593574252

Note

In the first example, f(10, 1) = g(1, 2) ⋅ g(1, 5) = 1, f(10, 2) = g(2, 2) ⋅ g(2, 5) = 2.

In the second example, actual value of formula is approximately 1.597 ⋅ 10^{171}. Make sure you print the answer modulo (10^{9} + 7).

In the third example, be careful about overflow issue.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        private static final long MOD = (long) (1e9 + 7);

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int p;
            int x = in.nextInt();
            long n = in.nextLong();

            Maths.initializePrimeTable(100000);

            long result = 1;
            boolean found = false;
            for (int i = 2; (long) i * i <= x; i++) {
                if (x % i == 0) {
                    if (Maths.isPrime(i)) {
                        found = true;
                        p = i;
                        result = result * Maths.pow(p, calculate(n, p), MOD) % MOD;
                    }
                    if (i * i != x && Maths.isPrime(x / i)) {
                        found = true;
                        p = x / i;
                        result = result * Maths.pow(p, calculate(n, p), MOD) % MOD;
                    }
                }
            }

            if (!found) {
                result = result * Maths.pow(x, calculate(n, x), MOD) % MOD;
            }


            out.println(result);
        }

        private long calculate(long n, int p) {
            long sum = 0, d = p;
            while (n / d > 0) {
                sum = (sum + n / d) % (MOD - 1);
                if ((double) d * p > n) {
                    break;
                }
                d *= p;
            }
            return sum;
        }

    }

    static class InputReader {
        public final BufferedReader reader;
        public StringTokenizer tokenizer = null;

        public InputReader(Reader reader) {
            this.reader = new BufferedReader(reader, 32767);
        }

        public InputReader(InputStream inputStream) {
            this(new InputStreamReader(inputStream));
        }

        public String next() {
            if (hasNext()) return tokenizer.nextToken();
            else throw new NoSuchElementException();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public boolean hasNext() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String nextLine = reader.readLine();
                    if (nextLine == null) return false;
                    tokenizer = new StringTokenizer(nextLine);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.hasMoreTokens();
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        private OutputWriter(Writer writer, boolean autoFlush) {
            this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
        }

        public OutputWriter(Writer writer) {
            this(writer, true);
        }

        public OutputWriter(OutputStream outputStream) {
            this(new OutputStreamWriter(outputStream), false);
        }

        public OutputWriter println(long value) {
            writer.println(value);
            return this;
        }

        public void close() {
            writer.close();
        }

    }

    static class Maths {
        public static int[] primes = null;
        public static int[] phi = null;
        public static int numberOfPrimes = 0;

        private Maths() {
        }

        public static long pow(long a, long n, long p) {
            if (a == 0) {
                return 0;
            }
            long result = 1;
            while (n > 0) {
                if ((n & 1) == 1) result = result * a % p;
                a = a * a % p;
                n >>= 1;
            }
            return result;
        }

        public static void initializePrimeTable(int n) {
            if (numberOfPrimes != 0) {
                return;
            }
            primes = new int[n + 1];
            phi = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                if (phi[i] == 0) {
                    primes[numberOfPrimes++] = i;
                    phi[i] = i - 1;
                }
                for (int j = 0; j < numberOfPrimes && i * primes[j] <= n; j++) {
                    phi[i * primes[j]] = phi[i] * (i % primes[j] != 0 ? primes[j] - 1 : primes[j]);
                    if (i % primes[j] == 0) break;
                }
            }
        }

        public static boolean isPrime(int n) {
            if (phi != null && n < phi.length) return phi[n] == n - 1;
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) return false;
            }
            return true;
        }

    }
}

