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.
#
#
#
# h,w = map(int,input().split())
# r1 = list(map(int,input().split()))
# c1 = list(map(int,input().split()))
# l = []
#
# for i in range(h):
#     ka = [0]*(w)
#     l.append(ka)
# for i in range(len(r1)):
#     for j in range(r1[i]):
#         l[i][j] = -1
# for i in range(len(c1)):
#     for j in range(c1[i]):
#
#         l[j][i] = -1
#
#
# mod = 10**9 + 7
# ans = 0
# # for i in l:
# #     print(*i)
#
# for i in range(h):
#     count = 0
#     for k in range(len(l[i])):
#         if l[i][k] != -1:
#             break
#         else:
#             count+=1
#     if count!=r1[i]:
#         print(0)
#         exit()
#     for j in range(k+1,len(l[i])):
#       if l[i][j]!=-1:
#        l[i][j]+=1
#
# for i in range(w):
#     count = 0
#     for k in range(h):
#         if l[k][i] != -1:
#             break
#         else:
#             count+=1
#     if count!=c1[i]:
#         print(0)
#         exit()
#     for j in range(k+1,h):
#         if l[j][i] == 1 and l[j][i]!=-1:
#             l[j][i]+=1
#
# for i in range(h):
#     for j in range(w):
#         if l[i][j] == 2:
#             ans+=1
#
#
#
#
#
# if ans!=0:
#     print(pow(2,ans,mod))
# else:
#     print(0)


def solve(n,z):
    n1 = n
    count = 0
    ans = 0
    while n!=0:
        n = n//z
        count+=1

    prev = 0

    for i in range(count,0,-1):
        j = z**i
        z1 = ((n1 - j)//j) + 1
        # print(j,z1)
        yo = z1-prev
        prev+=yo
        ans+=i*yo
        # print(j,i*yo,z1,yo)
    # print(ans)
    return ans











import math

# A function to print all prime factors of
# a given number n
def primeFactors(n):
    ans = []
    # Print the number of two's that divide n
    while n % 2 == 0:
        ans.append(2)
        n = n / 2

    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    for i in range(3,int(math.sqrt(n))+1,2):

        # while i divides n , print i ad divide n
        while n % i== 0:
            ans.append(int(i))
            n = n / i

            # Condition if n is a prime
    # number greater than 2
    if n > 2:
        ans.append(int(n))

    return ans
mod = 10**9 + 7
x,n = map(int,input().split())
z = primeFactors(x)
z = sorted(set(list(z)))
fin = 1

for i in z:
    k = solve(n,i)
    fin*=pow(i,k,mod)
# print(z)
print(fin%mod)





