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.
//package learning;

import java.util.*;
import java.io.*;
import java.lang.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class NitsLocal {
    static ArrayList<String> s1;
    static boolean[] prime;
    static int n = (int)1e7;
    
     static void sieve() {
Arrays.fill(prime	, true);
prime[0] = prime[1] = false;
for(int i = 2 ; i * i <= n ; ++i) {
if(prime[i]) {
for(int k = i * i; k<= n ; k+=i) {
prime[k] = false;
}
}
}

}
    public static void main(String[] args) {
        InputReader sc = new InputReader(System.in);
        
           prime  = new boolean[n + 1];
sieve();
                prime[1] = false;
                /*
                int t = sc.ni();
                while(t-- > 0)
                {
                    int a = sc.ni();
                    int b = sc.ni();
                    int d = sc.ni();
                    
                    int p = (a + d + 1 - b)/2;
                    
                    if(p < 0)
                    {
                        p = 0;
                        //if(a > b)
                           // p = 1;
                    }
                    w.println(p);
                    
                }
                
                 */
               
                int x = sc.ni();
                long n = sc.nl();
                fac = new HashSet<>();
                primeFactors(x);
                Iterator itr = fac.iterator();
                long ans = 1l;
                long mod = 1000000007;
                long [][]lim = new long[fac.size()][1];
                
                
                int k1 = 0;
                while(itr.hasNext())
                {
                    Integer p = (Integer) itr.next();
                    
                   long ct=0;
			for(int j=1;;j++) {
				long add=n/pow((long)p,(long)j);
                                
				ct+=add;
				if(add==0) break;
			if(n/(long)p<pow(p,(long)j)) break;
			}
                    
                    ans = (ans*modexp(p,ct,mod))%mod;
                }
               w.println(ans);
                
      
       w.close();
       
        
    }
    public static long pow(long i, long j) {
		long res=1L;
		for(int a=0;a<j;a++) res*=i;
		return res;
	}
    public static long powmod(long i, long j,long MOD) {
		if(j==0) return 1L;
		if(j%2==0) {
			long temp=powmod(i,j/2,MOD);
			return (temp*temp)%MOD;
		}
		return (i*powmod(i,j-1,MOD))%MOD;
	}
    static HashSet<Integer> fac;
    public static void primeFactors(int n) 
    { 
        // Print the number of 2s that divide n 
        int t = 0;
        while (n%2==0) 
        { 
            fac.add(2);
            n /= 2; 
        } 
  
        // n must be odd at this point.  So we can 
        // skip one element (Note i = i +2) 
        for (int i = 3; i*i <= n; i+= 2) 
        { 
            // While i divides n, print i and divide n 
            while (n%i == 0) 
            { 
                fac.add(i);
                n /= i; 
            } 
        } 
  
        // This condition is to handle the case whien 
        // n is a prime number greater than 2 
        if (n > 2) 
            fac.add(n);
    } 
     static long modexp(long x,long n,long M)
{
    long power = n;
    long result=1;
    x = x%M;
    while(power>0)
    {
        if(power % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        power = power/2;
    }
    return result;
}
    static int gcd(int a,int b)
    {
        if(a==0)
            return b;
        else
            return gcd(b%a,a);
    }
    static class Temp{
        int a;
        int b;
        int d;
        Temp(int a,int b,int d)
        {
            this.a = a;
            this.b = b;
            this.d = d;
        }
    }
    static class Query{
        int p;
        int index;
        int value;
        public Query(int p,int index,int value)
        {
            this.p = p;
            this.index = index;
            this.value = value;
            
        }
    }
    static int nextPowerOf2(int n) 
    { 
        int count = 0; 
  
        // First n in the below  
        // condition is for the  
        // case where n is 0 
        if (n > 0 && (n & (n - 1)) == 0) 
            return n; 
  
        while(n != 0) 
        { 
            n >>= 1; 
            count += 1; 
        } 
  
        return 1 << count; 
    } 
    
   static long sum1(int t1,int t2,int x,int []t)
   {
       int mid = (t2-t1+1)/2;
  if(t1==t2)
      return 0;
    
   else
   return sum1(t1,mid-1,x,t) + sum1(mid,t2,x,t);
    
     
   }
  
   
    static String replace(String s,int a,int n)
    {
        char []c = s.toCharArray();
        for(int i=1;i<n;i+=2)
        {
            int num = (int) (c[i] - 48);
            num += a;
            num%=10;
            c[i] = (char) (num+48);
        }
        return new String(c);
    }
    static String move(String s,int h,int n)
    {
        h%=n;
        char []c = s.toCharArray();
        char []temp = new char[n];
        for(int i=0;i<n;i++)
        {
            temp[(i+h)%n] = c[i];
        }
        return new String(temp);
    }
    
     public static int ip(String s){
return Integer.parseInt(s);
}
     static class multipliers implements Comparator<Long>{
  
         
  public int compare(Long a,Long b) {
   if(a<b)
    return 1;
   else if(b<a)
    return -1;
   else
    return 0;
  }
 }
     static class multipliers1 implements Comparator<Student>{
  
  public int compare(Student a,Student b) {
   if(a.y<b.y)
    return 1;
   else if(b.y<a.y)
    return -1;
   else
   {
       if(a.id < b.id)
           return 1;
       else if(b.id<a.id)
           return -1;
       else
           return 0;
           
    //return 0;
   }
  }
 }
    // Java program to generate power set in 
// lexicographic order. 

    
    
    
      static class InputReader {
 
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
 
public InputReader(InputStream st) {
this.stream = st;
}
 
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
 
public int ni() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
 
public long nl() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
 
public int[] nia(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = ni();
}
return a;
}
 
public String rs() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
 
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
 
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
 
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
 
}





   
static PrintWriter w = new PrintWriter(System.out);
                  static class Student
    {
        int id;
        //int x;
       
        int y;
        //long z;
        
        Student(int id,int y)
        {
            this.id = id;
            //this.x = x;
            //this.s = s;
            this.y = y;
           // this.z = z;
            
            
            
        }
        
    }
}
