#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;
  cin>>A>>B>>N;
  mint t[B+1],ans=1;
  mint2 t2[B+1];
  for(int i=B;i>=1;i--){
    t[i]=mint(B/i-(A-1)/i).pow(N);
    t2[i]=mint2(B/i-(A-1)/i).pow(N);
    for(int j=2*i;j<=B;j+=i){
      t[i]-=t[j];
      t2[i]-=t2[j];
    }
    ans*=mint(i).pow(t2[i].val());
  }
  cout<<ans.val()<<endl;
}