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.util.*;
import java.io.*;
import java.math.BigInteger;
import java.text.*;

public class C1228 {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);

		int x = sc.nextInt();
		int xx = x;
		BigInteger n = BigInteger.valueOf(sc.nextLong());
		int mod = (int) 1e9 + 7;
		sieve((int) Math.sqrt(x) + 1);

		int[] cnt = new int[primes.size()];
		int idx = 0;
		for (int p : primes) {
			while (x % p == 0) {
				x /= p;
				cnt[idx]++;
//				pw.println(p);
			}
			idx++;
		}
		BigInteger ans = BigInteger.ONE;
//		pw.println(x);

		for (int i = 0; i < cnt.length; i++) {
			int prime = primes.get(i);
			BigInteger mult = BigInteger.valueOf(prime);
			BigInteger e = BigInteger.ZERO;
			if (cnt[i]-- > 0) {
				while (true) {
					if (n.divide(mult).compareTo(BigInteger.ZERO) == 0)
						break;
					e = e.add(n.divide(mult));
					mult = mult.multiply(BigInteger.valueOf(prime));

				}
			}
			ans = ans.multiply(BigInteger.valueOf(prime).modPow(e, BigInteger.valueOf(mod)));
			ans = ans.mod(BigInteger.valueOf(mod));
		}
		int prime = x;
//		pw.println(prime);
		BigInteger mult = BigInteger.valueOf(prime);
		BigInteger e = BigInteger.ZERO;
		if(x!=1) {
		while (true) {
			if (n.divide(mult).compareTo(BigInteger.ZERO) == 0)
				break;
			e = e.add(n.divide(mult));
			mult = mult.multiply(BigInteger.valueOf(prime));
		}
			ans = ans.multiply(BigInteger.valueOf(prime).modPow(e, BigInteger.valueOf(mod)));
			ans = ans.mod(BigInteger.valueOf(mod));

		
		}
		pw.println(ans.mod(BigInteger.valueOf(mod)));
		pw.close();

	}

	static long modPow(long base, long exp, long mod) {
		long x = 1;
		while (exp > 0) {
			if (exp % 2 == 1)
				x = (x * base) % mod;
			base = (base * base) % mod;
			exp = exp / 2;
		}
		return x;
	}

	static boolean[] isPrime;
	static ArrayList<Integer> primes;

	public static void sieve(int N) {
		isPrime = new boolean[N + 1];
		primes = new ArrayList<Integer>();
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
		for (int i = 2; 1l * i * i <= N; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j <= N; j += i) {
					isPrime[j] = false;
				}
			}
		}
		for (int i = 2; i < isPrime.length; i++) {
			if (isPrime[i])
				primes.add(i);
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}
