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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;


public class wef {
public static class FastReader {
	BufferedReader br;
	StringTokenizer st;
	//it reads the data about the specified point and divide the data about it ,it is quite fast
	//than using direct 

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

	String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception r) {
				r.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());//converts string to integer
	}

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

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

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (Exception r) {
			r.printStackTrace();
		}
		return str;
	}
}
static ArrayList<String>list1=new ArrayList<String>();
static void combine(String instr, StringBuffer outstr, int index,int k)
{
	if(outstr.length()==k)
	{
		list1.add(outstr.toString());return;
	}
	if(outstr.toString().length()==0)
	outstr.append(instr.charAt(index));
    for (int i = 0; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
       
        combine(instr, outstr, i + 1,k);
        outstr.deleteCharAt(outstr.length() - 1);
    }
   index++;
} 
static ArrayList<ArrayList<Integer>>l=new ArrayList<>();
static void comb(int n,int k,int ind,ArrayList<Integer>list)
{
	if(k==0)
	{
		l.add(new ArrayList<>(list));

		return;
	}
	
	
	for(int i=ind;i<=n;i++)
	{
		list.add(i);
		comb(n,k-1,ind+1,list);
		
		list.remove(list.size()-1);
		
	}
	
	
	
	
	

}
static long sum(long n)
{
	long sum=0;
	while(n!=0)
	{
		sum+=n%10;
		n/=10;
	}
	return sum;
}


static boolean check(HashMap<Integer,Integer>map)
{
	for(int h:map.values())
		if(h>1)
			return false;
	return true;
}

static class Pair implements Comparable<Pair>{
    int x;int y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
      //  this.i=i;
    }
	@Override
	public int compareTo(Pair o) {
		// TODO Auto-generated method stub
		return x-o.x;
		
	}
}
static long ncr(long n, int k) 
{ long m=(long)1e9+7;
    long C[] = new long[k + 1]; 
     
    // nC0 is 1 
    C[0] = 1;   
   
    for (int i = 1; i <= n; i++) 
    { 
        // Compute next row of pascal  
        // triangle using the previous row 
        for (int j = Math.min(i, k); j > 0; j--) 
            C[j] = (C[j]%m + C[j-1]%m)%m; 
    } 
    return C[k]%m; 
} 
static boolean isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
    // This is checked so  
    // that we can skip 
    // middle five numbers 
    // in below loop 
    if (n % 2 == 0 ||  
        n % 3 == 0) 
        return false; 
  
    for (int i = 5; 
             i * i <= n; i = i + 6) 
        if (n % i == 0 || 
            n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 
static long pow(long a, long n, long mod) {
	//		a %= mod;
	long ret = 1;
	int x = 63 - Long.numberOfLeadingZeros(n);
	for (; x >= 0; x--) {
		ret = ret * ret % mod;
		if (n << 63 - x < 0)
			ret = ret * a % mod;
	}
	return ret;
}

static long gcd(long a, long b) 
{ 
  if (b == 0) 
    return a; 
  return gcd(b, a % b);  
} 
static long prod(long n,long pr,long mod)
{
	long p=0;
	while(n>0)
	{
		p+=n/pr;
		n=n/pr;
	}
	return pow(pr,p,1000000007L);
}
public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	FastReader in=new FastReader();
	TreeMap<Long,Integer>map=new TreeMap<Long,Integer>();
	ArrayList<Integer>list=new ArrayList<Integer>();
	HashSet<Integer>set=new HashSet<Integer>();
	HashSet<Integer>dis=new HashSet<Integer>();
	
	long x=in.nextLong();long m=x;
	long n=in.nextLong();
	//long count=prime(x);
	long ans=1;long mod=(long) (1e9+7);
	if(x%2==0)
	{	ans=(ans%mod*prod(n,2,mod)%mod)%mod;
		
	//	ans=(ans%mod*count%mod)%mod;count--;
		while(x%2==0)
			x/=2;
	}
	
	for(long i=3;i<=Math.sqrt(x);i+=2)
	{
		if(x%i==0)
		{	ans=(ans%mod*prod(n,i,mod)%mod)%mod;//System.out.println(1146199967%mod);
				
		//	ans=(ans%mod*count%mod)%mod;count--;
			while (x % i == 0) 
	            x /= i; 
		}
		
	}
	//System.out.println(x);
	if(x>2)
	{
		
			ans=(ans%mod*prod(n,x,mod)%mod)%mod;
			
	}
	
	System.out.println(ans);
	
	
	}
}
