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.*;
import static java.lang.Math.*;
import java.util.*;
public class Mao {
static Reader  in=new Reader();
static long mx=0,mz=1000000007L;
static StringBuilder sd=new StringBuilder();
    public static void main(String [] args) {
   List<Long>Prime=new ArrayList<>();
   long x=in.l(),n=in.l(),ans=1L;
   if(x%2==0){Prime.add(2L);
   while(x%2==0){x/=2;}
   }
   for(long i=3;i*i<=x;i+=2){
      if(x%i==0){Prime.add(i);
   while(x%i==0){x/=i;}
   }
   }
   if(x>1){
   Prime.add((long)x);
   }
   for(int i=0;i<Prime.size();i++){
   long num=(long)Prime.get(i),lol=0;
   for(long wow=num;wow<=n;wow*=num){
   lol=(n/wow);
   long an=MuiltP((long)num,(long)lol)%mz;
       ans=(ans*an)%mz;
   if(n/num<wow)break;
   }
       
   }
        System.out.println(ans%mz);
    }
    static long MuiltP(long wow, long P){
        if(P==0){return 1;}
        if(P==1){return wow;}
        long lol=MuiltP(wow,P/2)%mz;
        if(P%2==0)
            return (lol*lol)%mz;
        return ((lol*lol%mz)*wow)%mz;
    }
   static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        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 String s(){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 long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
    
}
class node implements Comparable<node> {
    int x;
    String S;
    node(int x,String S){
    this.x=x;
    this.S=S;}

    
    @Override
    public int compareTo(node o) {
        return x-o.x;}
}
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 int high = array[0];
 
 int low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
 
}
class Segment_Tree{
    long n,a[];
    long seg[],lazy[];
    Segment_Tree(int n,long a[]){
        this.n=n;
        lazy=new long[4*n];
    this.a=a;
    seg=new long[n*4];
    build(1,0,n-1);
    }
        void build(int p,int s,int e) {
        if(s==e) {
            seg[p] = a[s];
            return;
        }
        
        build(2*p,s,(s+e)/2);
        build(2*p+1,(s+e)/2+1,e);
        
        seg[p] = min(seg[2*p], seg[2*p+1]);
    }
    
        void update(int p,int s,int e,int i,int v) {
        if(s==e) {
            seg[p] = v;
            return;
        }
        
        
        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
        else update(2*p+1,(s+e)/2+1,e,i,v);
        
        seg[p] = min(seg[2*p],seg[2*p+1]);
    }
        void check(int p,int s,int e) {
        if(lazy[p]!=0) {
            seg[p] += lazy[p];
            if(s!=e) {
                lazy[2*p] += lazy[p];
                lazy[2*p+1] += lazy[p];
            }
            lazy[p] = 0;
        }
    }
    void update(int p,int s,int e,int a,int b,int v) {
        check(p,s,e);
        
        if(s>=a && e<=b) {
            seg[p] += v;
            
            if(s!=e) {
                lazy[2*p] += v;
                lazy[2*p+1] += v;
            }
            
            return;
        }
        
        if(s>b || e<a)
            return;
        
        update(2*p,s,(s+e)/2,a,b,v);
        update(2*p+1,(s+e)/2+1,e,a,b,v);
        
        seg[p] = min(seg[2*p],seg[2*p+1]);
    }
    
        long get(int p,int s,int e,int a,int b) {
        check(p,s,e);
        
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return Integer.MAX_VALUE; 
        
        return min(get(2*p,s,(s+e)/2,a,b), get(2*p+1,(s+e)/2+1,e,a,b));
    }
}