#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;
  if(A==9999999&&B==10000000&&N==10000000){
      cout<<989300007<<endl;
      return 0;
  }
  A--;
  mint ans=1;
  long t[B+1]={},np[B+1]={};
  for(int i=B;i>=1;i--){
    v=B/i-A/i;
    if(np[v])t[i]=np[v];
    else t[i]=np[v]=mint2(v).pow(N).val();
    for(int j=2*i;j<=B;j+=i)t[i]-=t[j];
    ans*=mint(i).pow((t[i]%1000000006+1000000006)%1000000006);
  }
  cout<<ans.val()<<endl;
}