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.
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:31/05/2020

'''
import sys
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def read():
    tc=1
    if tc:
        input=sys.stdin.readline
    else:
        sys.stdin=open('input1.txt', 'r')
        sys.stdout=open('output1.txt','w')


def powermod(a,b,m):
    a%=m
    res=1
    if(a==0):
        return 0
    while(b>0):
        if(b&1):
            res=(res*a)%m;
        b=b>>1
        a=(a*a)%m;
    return res


def isprime(n):
    if(n<=1):
        return 0
    for i in range(2,int(sqrt(n))+1):
        if(n%i==0):
            return 0
    return 1


def solve():
    
    x,n=mi()
    p=[]
    if isprime(x):
        p.append(x)
    else:
        for i in range(2,int(sqrt(x))+1):
            if(x%i==0):
                if isprime(i):
                    p.append(i)
                if i!=x//i and isprime(x//i):
                    p.append(x//i)

    # print(p)
    div=[]
    for i in p:
        x=i
        while(n>=x):
            x*=i
        x//=i
        c=0
        while(x>=i):
            c1=(n//x)-c
            c+=c1
            div.append([x,c1])
            x//=i
    

    ans=1

    for i in div:
        ans=(ans*powermod(i[0],i[1],mod))%mod
    print(ans)
    
    
    
    
    
    
        










    
    
if __name__ =="__main__":
    read()
    solve()
