题意：
定义f(i)=∑ k∣i k^d(i≤n)，给出q个询问，每个询问询问区间[l,r]的f(i)的和。
n<=1e7 d<=1e18 q<=5e4
可以发现f(i)是个积性函数，那么我们就可以欧拉筛 O(n) 预处理出f(i)，然后做个前缀和就行了。
f(i)分为三种情况:
1.i为素数 f(i)=i^d
2.i%p[j]!=0 f(i*pj)=f(i)*f(p[j])
3.i%p[j]==0 这个比较复杂，以下是f老板说的：我们要考虑的是i*p[j]比i多的约数是什么，假设i*p[j]是p[j]的k次，那多出来的约数都是p[j]^k再乘个数，否则已经被i包含了，那只要考虑这些数的贡献就行，也就是f(i*p[j]/p[j]^k)*(p[j]^k)^d
//by zykykyk
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define rg register
#define il inline
#define vd void
#define ll long long
#define mod 1000000007
#define maxn 10000010
#define For(i,x,y) for (rg int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (rg int i=(x);i>=(y);i--)
#define cross(i,k) for (rg int i=first[k];i;i=last[i])
using namespace std;
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll read(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,tot,q,x,P[maxn],minp[maxn],minpd[maxn],sum[maxn];
bool vis[maxn];
ll d;
il int power(int x,ll y){
int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod) if (y&1) ans=1ll*ans*x%mod;
return ans;
}
il vd init(){
n=read(),d=read(),q=read();
sum[1]=1;
For(i,2,n){
if (!vis[i]) P[++tot]=minp[i]=i,minpd[i]=sum[i]=power(i,d),sum[i]=(sum[i]+1)%mod;
for (int j=1;i*P[j]<=n&&j<=tot;j++){
int k=i*P[j];
vis[k]=1;
if (i%P[j]==0){
minp[k]=minp[i]*P[j];
minpd[k]=1ll*minpd[i]*minpd[P[j]]%mod;
sum[k]=(sum[i]+1ll*minpd[k]*sum[k/minp[k]]%mod)%mod;
break;
}
else {
minp[k]=P[j];
minpd[k]=minpd[P[j]];
sum[k]=1ll*sum[i]*sum[P[j]]%mod;
}
}
}
For(i,2,n) (sum[i]+=sum[i-1])%=mod;
}
int l,r;
il vd work(){
while (q--){
l=read(),r=read();
printf("%d
",((sum[r]-sum[l-1])%mod+mod)%mod);
}
}
int main(){
init(),work();
}