A,B,N=map(int,input().split())
Mod=10**9+7

Count=[-1]*(B+1)

for g in range(B,0,-1):
    alpha=B//g-(A-1)//g
    L=pow(alpha,N,Mod)

    j=2*g
    while j<=B:
        L-=Count[j]
        j+=g
    Count[g]=L%Mod

T=1
for g,x in enumerate(Count[1:],1):
    T*=pow(g,x,Mod)
    T%=Mod
print(T)