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) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10$,  $f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63$. 

You have integers $x$ and $n$. Calculate $f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}$.


-----Input-----

The only line contains integers $x$ and $n$ ($2 \le x \le 10^{9}$, $1 \le n \le 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) \cdot g(1, 5) = 1$, $f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$.

In the second example, actual value of formula is approximately $1.597 \cdot 10^{171}$. Make sure you print the answer modulo $(10^{9} + 7)$.

In the third example, be careful about overflow issue.

Difficulty: interview

Starter code:

Solutions:
x, n = list(map(int, input().split()))

def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

pf = primeFactor(x)
mod = 10 ** 9 + 7
def calc(p):
    s = 0
    a = n//p
    while a:
        s += a
        a //= p
    return pow(p, s, mod)

ans = 1
for p in pf:
    ans = ans * calc(p) % mod
print(ans)




import sys
input = sys.stdin.readline

x,n=list(map(int,input().split()))
mod=10**9+7

import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

ANS=1

for f in FACT:
    for k in range(1,70):
        t=n//(f**k)
        if t==0:
            break
        ANS=ANS*pow(f,t,mod)%mod

print(ANS)


from math import sqrt, ceil
def primes(x):
    ox = x
    l = []
    cp = 3
    if x % 2 == 0:
        l.append(2)
    while x % 2 == 0:
        x //= 2
    while cp <= ceil(sqrt(ox)):
        if x % cp == 0:
            l.append(cp)
        while x % cp == 0:
            x //= cp
        cp += 2
    if x != 1:
        l.append(x)
    return l

mo = 10**9+7
x,n = list(map(int,input().split()))
pi = primes(x)
s = 1
for p in pi:
    pk = p
    while pk <= n:
        s *= pow(p,n//pk,mo)
        s %= mo
        pk *= p
print(s)


x,n=[int(x) for x in input().split()]
prime=set()
arr=1
y=int(x**0.5)
for i in range(2,y+1):
    while x%i==0:
        prime.add(i)
        x//=i
if x!=1:
    prime.add(x)
dic={}
for item in prime:
    dic[item]=0
for item in prime:
    for i in range(1,60):
        dic[item]+=n//(item**i)
for item in dic:
    arr*=pow(item,dic[item],(10**9+7))
print(arr%(10**9+7))
        


def primefactor(p):
    x=p
    pf=[]
    for i in range(2,int(p**0.5)+1):
        if(x%i==0):
            pf.append(i)
            while(x%i==0):
                x//=i
    if x>1:
        pf.append(x)
    return pf
ans=1
MOD=int(1e9+7)
x,n=list(map(int,input().split()))
for p in primefactor(x):
    exp=0
    P=p
    while(P<=n):
        exp+=n//P
        P*=p
    ans*=pow(p,exp,MOD)
    ans%=MOD
print(ans)


def factor(n):
    out = []
    
    power = 0
    while n & 1 == 0:
        power += 1
        n >>= 1

    if power:
        out.append(2)
        power = 0

    test = 3
    while pow(test,2) <= n:
        while n % test == 0:
            power += 1
            n //= test
        if power:
            out.append(test)
            power = 0
        test += 2

    if n > 1:
        out.append(n)

    return out


x, n = list(map(int,input().split()))

M = 10 ** 9 + 7

f = factor(x)
out = 1
for p in f:
    newPower = 0
    nCopy = n
    while nCopy:
        nCopy //= p
        newPower += nCopy
    out *= pow(p,newPower,M)
    out %= M

print(out)


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

x,n = inpl()

divs = set()
div = 2
while div*div <= x:
    while x%div == 0:
        divs.add(div)
        x //= div
    div += 1

if x != 1:
    divs.add(x)

ans = 1
for div in divs:
    tmp = 1
    while tmp <= n:
        tmp *= div
        ans *= pow(div,n//tmp,mod)
        ans %= mod

print(ans%mod)


MOD = 10**9 + 7
x, n = [int(item) for item in input().split()]
def prime_factorize(n):
    b = 2
    fct = set() 
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.add(b)
        b = b + 1
    if n > 1:
        fct.add(n)
    return fct

fac = prime_factorize(x)
ans = 1
for f in fac:
    cnt = 0
    val = n
    while val:
        cnt += val // f
        val //= f
    ans *= pow(f, cnt, MOD)
    ans %= MOD

print(ans)

def prime_divs(n):
    divs = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            divs.append(d)
            while n % d == 0:
                n //= d
        d += 1
    if n > 1:
        divs.append(n)
    return divs


def pwrmod(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return (pwrmod(a, n // 2) % MOD) ** 2
    return pwrmod(a, n - 1) * a % MOD


x, n = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 1
for d in prime_divs(x):
    pwrsum = 0
    pwr = d
    while pwr <= n:
        pwrsum += n // pwr
        pwr *= d
    ans = ans * pwrmod(d, pwrsum) % MOD
print(ans)

x, n = map(int, input().split())
mod = 1000000007
res = 1

def bpow(x, y):
    res = 1
    while y > 0:
        if y % 2 == 1:
            res = (res * x) % mod
            y -= 1
        else:
            x = (x * x ) % mod
            y //= 2
    return res

sp = []
i = 2

while i * i <= x:
    if x % i == 0:
        sp.append(i)
        while x % i == 0:
            x //= i
    i += 1
    
if (x > 1):
    sp.append(x)

for i in sp:
    st = 1
    while st <= n:
        st *= i
    st //= i
    byv = 0
    while st > 0:
        cnk = n // st
        cnk -= byv
        res = (res * bpow(st, cnk)) % mod
        byv += cnk
        st //= i

print(res)

from sys import stdin, stdout
 
ii = lambda: int(stdin.readline())
mi = lambda: list(map(int, stdin.readline().strip().split()))
li = lambda: list(mi())

MOD = int(1000000007)

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

x, n = mi()
fac = []
tmp = int(x)
if (tmp % 2 == 0):
	fac.append(2)
	while(tmp % 2 == 0):
		tmp = tmp // 2
i = 3
while (i * i <= tmp):
	if (tmp % i == 0):
		fac.append(i)
		while(tmp % i == 0):
			tmp = tmp // i
	i += 2

if (tmp > 2):
	fac.append(tmp)
ans = 1
for p in fac:
	prod = p
	i = 1
	fin = 0
	while (prod <= n):
		times = (n // prod) - (n // (prod * p))
		fin += (i * times)
		prod *= p
		i += 1
	ans = (ans * binpow(p, fin, MOD)) % MOD
print(ans)


import math

X, N = map(int, input().split())

def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

def main():
    NUM = {}
    for num in prime(X).keys():
        a = N
        c = 0
        while a > 0:
            a //= num
            c += a
        NUM[num] = c

    mod = int(1E9+7)
    ans = 1
    for num, c in NUM.items():
        ans = (ans * power_func(num, c, mod)) % mod

    print(ans)

def __starting_point():
    main()
__starting_point()

from itertools import chain
from math import sqrt

ub = 10**5
ub_sqrt = int(sqrt(ub))+1
primes = {2, 3} | set(chain(list(range(5, ub, 6)), list(range(7, ub, 6))))
du = primes.difference_update
for n in chain(list(range(5, ub_sqrt, 6)), list(range(7, ub_sqrt, 6))):
    if n in primes:
        du(list(range(n*3, ub, n*2)))


x, n = list(map(int, input().split()))
divisors = []
for p in primes:
    if x % p == 0:
        divisors.append(p)
        while x % p == 0:
            x //= p
if x > 1:
    divisors.append(x)

ans = 1
mod = 10**9+7

for d in divisors:
    cur = d
    while cur <= n:
        ans = ans * pow(d, n//cur, mod) % mod
        cur *= d

print(ans)


#589_C

#import time

#start = time.time()

import math

md = (10 ** 9) + 7

def bin(n):
    l = math.floor(math.log(n, 2))
    s = ""
    while l >= 0:
        if n >= 2 ** l:
            n -= 2 ** l
            s += "1"
        else:
            s += "0"
        l -= 1
    return s

def ex(n, m):
    bn = bin(m)
    sm = n
    sms = []
    ssm = 1
    for i in range(len(bn) - 1, -1, -1):
        if bn[i] == "1":
            ssm = (ssm * sm) % md
        sm = (sm * sm) % md
    return ssm

ln = [int(i) for i in input().split(" ")]
x = ln[0]
n = ln[1]

div = []

def pf(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return [i] + pf(n // i)
    return [n]

dv = pf(x)

dv = sorted(dv)

ndv = [[dv[0], 1]]

for i in range(1, len(dv)):
    if dv[i] != dv[i - 1]:
        ndv.append([dv[i], 1])
    else:
        ndv[-1][1] += 1

sm = 1
for i in range(0, len(ndv)):
    nm = math.floor(math.log(n, ndv[i][0])) + 1
    for j in range(1, nm + 1):
        fs = n // (ndv[i][0] ** j)
        if fs == 0:
            continue
        nm = ndv[i][0]

        nn = ex(nm, fs)

        sm = (sm * nn) % md
        #print(sm, i)
print(sm)



import math
n,m=[int(x) for x in input().split()]
a=[]
for i in range(2, int(math.sqrt(n)) + 1): 
    while (n % i == 0): 
        a.append(i)
        while(n%i==0):
          n//= i 
if (n != 1): 
    a.append(n)
ans=1
for i in a:
  k=i
  while(m>=k):
    ans*=pow(i,m//k,1000000007)
    ans%=1000000007
    k*=i
print(ans%1000000007)


x, n = input().split(' ')
x, n = int(x), int(n)

primes = []

for i in range(2, 100000):
    if x % i == 0:
        primes.append(i);
        while x % i == 0:
            x = x // i

if x != 1:
    primes.append(x)

result_list = []
MOD = 1000000007

for p in primes:
    result = 0
    pk = p
    while pk <= n:
        result += n // pk
        pk *= p
    result_list.append((result, p))


def power (a, b):
    nonlocal MOD
    if b == 0:
        return 1
    r = 1
    ak = a
    while b > 0:
        if b % 2 == 1:
            r *= ak
        b = b // 2
        ak *= ak
        ak %= MOD
        r %= MOD
    return r


result = 1
for r, p in result_list:
    result *= power (p, r)
    result %= MOD


print (result)





import math

x, n = map(int, input().split())

maxPrime = int(math.sqrt(x) + 1)

isPrime = [True] * maxPrime

primes = []

for i in range(2, maxPrime):
  if(x % i == 0):
    primes.append(i)

  while (x % i) == 0:
    x = x // i

if(x > 1):
  primes.append(x)

sol = 1

def quickPow(x, power):
  if(power == 1):
    return x
  
  ans = quickPow(x , power // 2)
  
  ans *= ans

  if(power % 2) == 1:
    ans *= x
  
  return ans % 1000000007
  

for prime in primes:
  i = prime

  while(i <= n):
    sol = (sol * quickPow(prime % 1000000007, (n // i))) % 1000000007
    i *= prime

print(sol)

# MOD = 10**180
MOD = 1000000007

x, n = map(int, input().split())

def po(n, p):
	if p == 0: return 1
	if p == 1: return n % MOD
	p2 = p//2
	if p % 2 == 0: return (po(n, p2)**2) % MOD
	else: return (n * po(n, p2)**2) % MOD

def f(s, x, n):
	if x == 1: return 1
	sx = int(x**0.5)
	for p in range(s, sx+1):
		if x % p == 0:
			while x % p == 0:
				x //= p
			res = f(p+1, x, n)
			m = 0
			pp = p
			while n // pp > 0:
				m = (m + n // pp)
				pp *= p
			pm = po(p, m)
			res = (res*pm) % MOD
			return res
	m = 0
	pp = x
	while n // pp > 0:
		m = (m + n // pp)
		pp *= x
	return po(x, m) % MOD

res = f(2, x, n)
print(res)

MOD = int(1e9 + 7)

def log_power(base, exp):
    if exp == 0:
        return 1
    elif exp == 1:
        return base % MOD

    if exp % 2 == 1:
        return base * log_power(base, exp - 1) % MOD

    root = log_power(base, exp // 2)
    return root * root % MOD


def total(fact, limit):
    prod = 1
    power = fact

    while power <= limit:
        prod = prod * log_power(fact, limit // power) % MOD
        prod %= MOD
        power *= fact

    return prod


def solve(num, limit):
    fact = 2
    prod = 1

    while fact * fact <= num:
        count = 0
        while num % fact == 0:
            num //= fact
            count += 1

        if count > 0:
            prod = (prod * total(fact, limit)) % MOD
        fact += 1

    if num > 1:
        prod = (prod * total(num, limit)) % MOD

    return prod


def __starting_point():
    num, limit = list(map(int, input().split()))
    print(solve(num, limit))

__starting_point()

x,n=list(map(int,input().split()))
primes=[]
i=2
while i*i<=x:
    if x%i==0:
        primes.append(i)
    while x%i==0:
        x//=i
    i+=1
if x>1:
    primes.append(x)
mod=1000000007
ans=1
for i in range(len(primes)):
    prod=primes[i]
    while prod<=n:
        ans*=pow(prod,n//prod-n//(prod*primes[i]),mod);
        ans%=mod
        prod*=primes[i]
print(ans)


"""
NTC here
"""
from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10**7)
 
# print("Case #{}: {} {}".format(i, n + m, n * m))
 
 
def iin(): return int(stdin.readline())
 
 
def lin(): return list(map(int, stdin.readline().split()))

x,n=lin()
md=10**9+7
def factors(a):
    fact = []
    if a % 2 == 0:
        while a % 2 == 0:
            a //= 2
        fact.append(2)
    i = 3
    while i*i <= a:
        if a % i == 0:
            while a % i == 0:
                a //= i
            fact.append(i)
        i += 2
    if a > 1:
        fact.append(a)
    return fact

fact=factors(x)
ans=1
for f in fact:
    x=f
    ch=0
    while x<=n:
        ch+=n//x
        x*=f
    ans=ans*pow(f,ch,md)
    ans%=md  
ans=ans%md
print(ans)

from math import floor,sqrt
def pp(a,b,c):
	r = 1
	a%=c
	while(b):
		if b&1:
			r = (r*a) % c
		b>>=1
		a=(a*a)%c
	return r

n,x=[int(i)for i in input().split()]
d=n
l=[]
h=floor(sqrt(d))
MOD = (1000000007)
if(d%2==0):
	l+=[2];
	while d%2==0:d//=2;
for i in range(3,h+1,2):
	if(d%i==0):
		l+=[i]
	while(d%i==0):d//=i;

if d > 2: l+=[d]
ans = 1
for i in l:
	f = i
	s = 0
	while f <= x:
		s += x//f
		f *= i
	ans = (ans*pp(i,s,MOD))% MOD 
print(ans)

import heapq
from collections import defaultdict
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

X, Y = list(map(int, input().split()))


def primeFact_set(n):
    factors = set()
    i = 2
    while i*i <= n:
        if n % i == 0:
            n //= i
            if i <= Y:
                factors.add(i)
        else:
            i += 1
    if n > 1 and n <= Y:
        factors.add(n)
    return factors


X_prime = primeFact_set(X)
MOD = 10**9+7
ans = 1
for p in X_prime:
    tmp = p
    while tmp <= Y:
        div = Y//tmp
        ans *= pow(p, div, MOD)
        ans %= MOD
        tmp *= p
print(ans)


def factor(x):
    r = set()
    if x % 2 == 0:
        r.add(2)
    while x % 2 == 0:
        x //= 2
    for i in range(3, int(x ** .5 + 2), 2):
        if x % i == 0:
            r.add(i)
        while x % i == 0:
            x //= i
    if x != 1:
        r.add(x)
    return r
a, n = list(map(int, input().split()))
s = factor(a)
sol = 1
for i in s:
    t = i % 1000000007
    m = i
    while m <= n:
        sol = (sol * pow(t, n // m, 1000000007)) % 1000000007
        m = m*i
print(sol)


M = 10**9+7
x, n = list(map(int,input().split()))
import math
def primeFactors(n):
	primes = set()
	while n%2 == 0:
		primes.add(2)
		n//=2
	for i in range(3,int(math.sqrt(n))+1,2):
		while(n%i==0):
			primes.add(i)
			n//=i
	if(n>2):
		primes.add(n)
	return primes
def modexp( x, y, p ):
	res = 1
	while(y>0):
		if(y & 1):
			res*= x
			res%=p
		y >>= 1
		x%=p
		x*= x


	return res%p

primes = primeFactors(x)
ans = 1
for p in primes:
	cnt = 0;
	alphap = 1
	aux = n
	while(n/(p**alphap)>0):
		cnt += n//(p**alphap)
		alphap+=1
	
	cnt = cnt%(M-1)
	ans*= modexp(p,cnt,M)
	ans%=M
	

print(ans%M)