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.
// Created by Whiplash99
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class D
{
    private static final long MOD=1000000007;
    private static long multiply(long a, long b)
    {
        a%=MOD;
        b%=MOD;

        long res=0;
        while(b>0)
        {
            if((b&1)==1)
                res=(res+a)%MOD;
            a=(2*a)%MOD;
            b>>=1;
        }
        return res%MOD;
    }
    private static long pow2(long a, long b)
    {
        a%=MOD;
        b%=MOD-1;

        long res=1;

        while(b>0)
        {
            if((b&1)==1)
                res=(res*a)%MOD;

            a=(a*a)%MOD;
            b>>=1;
        }

        return res%MOD;
    }
    private static void pFact(long N, ArrayDeque<Long> primes)
    {
        for(long d=2;d*d<=N;d++)
        {
            int flag=0;
            while(N%d==0)
            {
                flag=1;
                N/=d;
            }
            if(flag==1)
                primes.addLast(d);
        }
        if(N>1)
            primes.addLast(N);
    }
    public static void main(String[] args) throws IOException
    {
        Reader r=new Reader();

        int i;

        long X=r.nextLong();
        long N=r.nextLong();
        BigInteger NN=new BigInteger(N+"");

        ArrayDeque<Long> primes=new ArrayDeque<>();
        pFact(X,primes);

        long ans=1;

        while(!primes.isEmpty())
        {
            long p=primes.pollFirst();
            long num=1;

            BigInteger NUM=new BigInteger(num+"");
            BigInteger P=new BigInteger(p+"");

            while(NUM.multiply(P).compareTo(NN)<=0)
            {
                num*=p;
                long times=N/num;
                ans=multiply(ans,pow2(p,times))%MOD;

                NUM=NUM.multiply(P);
            }
        }
        System.out.println(ans);
    }
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
        public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
        }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
        }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
        }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
        }public void close() throws IOException{if(din==null) return;din.close();}
    }
}