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 Mathematical;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class PrimeFunctiong {
    public static HashMap<Integer,Integer> getPrime(int x){
        int max=(int)Math.sqrt(x)+1;
        int seive[]=new int[max+1];
        HashMap<Integer,Integer> map=new HashMap<>();
        ArrayList<Integer> primes=new ArrayList<>();
        for(int i=2;i<=max;i++){
            if(seive[i]==0){
                for(int j=2*i;j<=max;j+=i){
                    seive[j]=1;
                }
                primes.add(i);
            }
        }
//        primes.add(x);
        for(int i=0;i<primes.size();i++){
            int prime=primes.get(i);
            while(x%prime==0){
                x=x/prime;
                map.put(prime,1);
//                System.out.println(x);
                if(x==1){
                    return map;
                }
            }
        }
        if(x!=1){
            map.put(x,1);
        }
        return map;
    }
    public static long power(long num,long p,long mod){
        if(p==0){
//            System.out.println("1");
            return 1;
        }
        if(p==1){
//            System.out.println(num);
            return num;
        }
        if(p%2==0){
            long small=1;
//            if(power.containsKey(p/2)){
//                small=power.get(p/2);
//            }
//            else{
                small=power(num,p/2,mod);
//            }
            long ans=((small%mod*small%mod)%mod);
//            power.put(p,ans);
//            System.out.println(ans);
            return ans;
        }
        else{
            long small=1;
//            if(power.containsKey(p/2)){
//                small=power.get(p/2);
//            }
//            else {
                small=power(num,p/2,mod);
//            }
            long ans=(small%mod*small%mod)%mod;
            ans=(ans%mod*num%mod)%mod;
//            power.put(p,ans);
//            System.out.println(ans);
            return ans;
        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String line[]=br.readLine().split(" ");
        int x=Integer.parseInt(line[0]);
        long n=Long.parseLong(line[1]);
//        System.out.println(n);
        HashMap<Integer,Integer> primes=getPrime(x);
//        System.out.println(primes.size());
        long ans=1;
        long mod=1000000007;
        for(int prime:primes.keySet()){
//            System.out.println(prime);
            long total=0;
            long curr=prime;
            long prev_curr=curr;
            while(n/curr!=0){
//                System.out.println(n/curr);
                long pow_curr=n/curr;
                curr*=prime;
//                System.out.println(curr);
//                total=(total%mod+pow_curr%mod)%mod;
                total=total+pow_curr;
                if(curr<=prev_curr){
                    break;
                }
                prev_curr=curr;

            }
//            HashMap<Long,Long> map=new HashMap<>();
//            System.out.println(total);
            long small_ans=power(prime,total,mod);
//            System.out.println(small_ans);
            ans=(ans%mod*small_ans%mod)%mod;
        }
//        System.out.println(power(2,10,mod));
//        System.out.println(power(2,11,mod));
        System.out.println(ans);
    }
}
