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.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;


/**
 * @authod Rashedul Hasan Rijul
 */
public class Soln {

    private static final long MOD = 1000000007L;
    FastReader fastReader;
    OutputStream outputStream = System.out;
    PrintWriter out;

    public Soln() {
    }

    public Soln(FastReader fastReader) {
        this.fastReader = fastReader;
        this.out = new PrintWriter(outputStream, true);
    }

    long bigMod(long b, long p, long m) {

        if (p == 0) return 1;
        if (p == 1) return (b % m);
        long ret = bigMod(b, p / 2, m);
        ret *= ret;
        ret %= m;

        if (p % 2 != 0) {
            ret *= b;
            ret %= m;
        }
        return ret;
    }

    long g(long n, long p) {

        long curr = p;
        long nextCurr;
        long ans = 1;

        while ((n / curr) != 0) {

            long cnt = n / curr;
            long b = curr;
            if (b > MOD) {
                b %= MOD;
            }

            if (curr > (n / p)) {
                ans = ans * bigMod(b, cnt, MOD);
                ans %= MOD;
                break;
            }

            nextCurr = curr * p;

            long rem = n / nextCurr;
            cnt -= rem;

            ans = ans * bigMod(b, cnt, MOD);
            if (ans > MOD) {
                ans %= MOD;
            }

            if (rem == 0) {
                break;
            }

            curr = nextCurr;
        }

        return ans;
    }

    private long solve() {

        long x = fastReader.nextLong();
        long n = fastReader.nextLong();

        long res = 1;

        if (x % 2L == 0) {
            x /= 2;
            res *= g(n, 2);
            res %= MOD;
            while (x % 2L == 0) {
                x /= 2L;
            }
        }
        for (long i = 3; (i * i) <= x; i += 2L) {

            if (x % i == 0) {
                res *= g(n, i);
                res %= MOD;
                while (x % i == 0) {
                    x /= i;
                }
            }
        }

        if (x != 1) {
            res *= g(n, x);
        }


        res %= MOD;

        return res;
    }

    public static void main(String args[]) throws FileNotFoundException, InterruptedException {

        // for testing in local
        // FastReader fastReader = FastReader.getFileReader("in.txt");

        FastReader fastReader = FastReader.getDefaultReader();
        Soln soln = new Soln(fastReader);

        System.out.println(soln.solve());

    }


    /**
     * TEMPLATE METHOD --------
     */
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        public static FastReader getFileReader(String fileName) throws FileNotFoundException {
            return new FastReader(new InputStreamReader(new FileInputStream(new File("in.txt"))));
        }

        public static FastReader getDefaultReader() throws FileNotFoundException {
            return new FastReader();
        }

        public FastReader(InputStreamReader inputStreamReader) {
            br = new BufferedReader(inputStreamReader);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}