A,B,N=map(int,input().split())
mod=10**9+7
ans=1
cnt=[0]*(B+1)
def make_divisors(n):
    lower_divisors,upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
for i in range(B,A-1,-1):
    if i==1:
        break
    x=B//i
    cnt[i]=pow(x,N,mod)
    for j in range(i*2,B+1,i):
        cnt[i]-=cnt[j]
for i,j in enumerate(cnt):
    ans*=pow(i,j,mod)
    ans%=mod
print(ans)