import sys
input = sys.stdin.readline
from math import sqrt
mod = 1000000007
def multiply(x,n):
if n == 1:
return x
xn2 = multiply(x,n//2)
if n%2:
return xn2*xn2*x %mod
else:
return xn2*xn2 %mod
N,M = map(int,input().split())
N1 = N
prime = {}
for p in range(2,int(sqrt(N))+1):
if N1%p:
continue
prime[p] = 0
while N1%p == 0:
N1 //= p
prime[p] += 1
if N1 != 1:
prime[N1] = 1
numer = 1
denom = 1
for p in prime:
numer *= multiply(p,prime[p]*M+1)-1
numer %= mod
denom *= p-1
denom %= mod
denom = multiply(denom,mod-2)
print(numer*denom %mod)
여러가지 수학지식을 섞어놓은 문제이다.
1. 등비수열의 합
2. 소인수 분해 (에라토스테네스의 체)
3. 분할정복을 이용한 거듭제곱
4. 모듈러 역원
을 이용해서 풀 수 있다.
오늘의 교훈) 모듈러 역원은 유용하다