int s[7d5],a,b,n,j;{Mint u=1;rd(a--,b,n);REP[s](p,Prime(b+1,s))for(ll q=p;j=b/q-a/q;q*=p)u*=Mint(p)**powmod(j,n,MD-1);wt(u);}