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.*;

public class Solution{
	static PrintWriter out=new PrintWriter(System.out);
	public static void main (String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp=br.readLine().trim().split(" ");
		
		int x=Integer.parseInt(temp[0]);
		long n=Long.parseLong(temp[1]);
		out.println(getResult(x,n));
		
		out.flush();
		out.close();
	}
	public static int getResult(int x,long n)
	{
	    int mod=1000000000+7;
	    ArrayList<Integer> primeFactors=new ArrayList<>();
	    for(int i=1;i<=Math.sqrt(x);i++){
	        if(x%i==0){
	            int d1=i;
	            int d2=x/i;
	            if(d1!=1 && isPrime(d1)){
	                primeFactors.add(d1);
	            }
	            if(d1!=d2 && isPrime(d2)){
	                primeFactors.add(d2);
	            }
	        }
	    }
	    int ans=1;
	    for(int i=0;i<primeFactors.size();i++){
	        long primeFactor=primeFactors.get(i);
	        int maxPower=(int)(Math.log(n)/Math.log(primeFactor));
	        long power=0;
	        long num=n;
	        while(num>0){
    	        long count=(num/primeFactor);
    	        power+=count;
    	        num/=primeFactor;
	        }
	        int temp=(power(primeFactor,power,mod));
            ans=(int)( ( 1L * (ans%mod) * (temp%mod) ) % mod );
	    }
	    return ans;
	}
	public static long pow(long a,long b){
	    if(b==0){
	        return 1;
	    }
	    long smallAns=pow(a,b/2);
	    long ans=smallAns*smallAns;
	    if(b%2!=0){
	        ans*=a;
	    }
	    return ans;
	}
	public static boolean isPrime(int x){
	    for(int i=2;i<=Math.sqrt(x);i++){
	        if(x%i==0){
	            return false;
	        }
	    }
	    return true;
	}
	public static int power(long a,long b,long mod)
	{
	    if(b==0){
	        return 1;
	    }
	    int smallAns=power(a,b/2,mod);
	    int ans=(int)((1L*(smallAns%mod)*(smallAns%mod))%mod);
	    if(b%2!=0){
	        ans=(int)((1L*(ans%mod)*(a%mod))%mod);
	    }
	    return ans;
	}
}