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 sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush,heappop,heapify
from itertools import permutations,combinations
from itertools import accumulate as ac
mod = int(1e9)+7
 
 
ip = lambda : int(stdin.readline())
inp = lambda: map(int,stdin.readline().split())
ips = lambda: stdin.readline().rstrip()
out = lambda x : stdout.write(str(x)+"\n")


#ans = 'Case #{}: {}'.format(_+1,ans)

def primeFactors(n):
    dic = dd(int)
    while n % 2 == 0:
        dic[2] += 1
        n = n // 2
    for i in range(3,int(math.sqrt(n))+1,2):
        while n % i== 0:
            dic[i] += 1
            n = n // i
    if n > 2:
        dic[n] += 1
    ele = sorted(list(dic.keys()))
    return ele

t = 1
for _ in range(t):
    x,n = inp()
    prime = primeFactors(x)
    ans = 1
    for i in prime:
        cur = i
        while cur<= n:
            if cur*i > n:
                break
            else:
                cur = cur*i

        if cur>n:
            pass
        else:
            count = n//cur
            ans *= pow(cur,count,mod)
            ans %= mod
            while True:
                cur = cur//i
                if cur == 1:
                    break
                new_count = n//cur
                new_count -= count
                ans *= pow(cur,new_count,mod)
                ans %= mod
                count = n//cur
    print(ans)
            
                
            
        

    

    

    
        
            

    
        
                

    
        
    
            
        
            
        
        
        
        
        
    
    
        
    

            
            
                
                    
                    
            
    
        
        
