#pragma GCC optimize ("O3","unroll-loops")
#pragma GCC target("avx512f")
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint=static_modint<1000000007>;
using mint2=static_modint<1000000006>;

int main(){
  int A,B,N,v;
  cin>>A>>B>>N;
  A--;
  mint ans=1;
  mint2 t[B+1];
  vector<mint2> np(B+1);
  for(int i=B;i>=1;i--){
    v=B/i-A/i;
    if(np[v].val())t[i]=np[v];
    else t[i]=np[v]=mint2(v).pow(N);
    for(int j=2*i;j<=B;j+=i)t[i]-=t[j];
    ans*=mint(i).pow(t[i].val());
  }
  cout<<ans.val()<<endl;
}