A,B,N=map(int,input().split())
mod=10**9+7
ans=1
cnt=[0]*(B+1)
for i in range(B,1,-1):
    if i==1:
        break
    x=B//i-(A-1)//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)