就 A 一个点，10 pts 了

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int mod=1e9+7,N=5e6;
int T,n,m,k,mu[N],pri[N],tot,vis[N],low[N],sum[N];
inline int read(){
    int ch=0,p=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar())if(c=='-')p=-1;
    for(;c>='0'&&c<='9';c=getchar())ch=ch*10+c-'0';
    return ch*p;
}
inline int qpow(int a,int b) {
    int ans=1;
    for(;b;b>>=1,a=a*a%mod) 
        if(b&1) 
            ans=ans*a%mod;
    return ans;
}
signed main(){
    T=read(),k=read();
    mu[1]=sum[1]=1;
    for(int i=2;i<N;++i){
        if(!vis[i]) mu[i]=-1,pri[++tot]=i,sum[i]=qpow(i,k)-1,low[i]=i;
        for(int j=1;j<=tot&&i*pri[j]<N;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                low[i*pri[j]]=low[i]*pri[j];
                mu[i*pri[j]]=0;
                if(low[i]==i) sum[i*pri[j]]=sum[i]*qpow(pri[j],k)%mod;
                else sum[i*pri[j]]=sum[i/low[i]]*sum[pri[j]*low[i]]%mod;
                break;
            }
            low[i*pri[j]]=pri[j];
            mu[i*pri[j]]=-mu[i];
            sum[i*pri[j]]=sum[i]*sum[pri[j]]%mod;
        }
    }
    for(int i=1;i<N;++i) 
        sum[i]=(sum[i-1]+sum[i])%mod; 
    while(T--){
        n=read(),m=read();
        int ans=0;
        for(int i=1,j;i<=min(n,m);i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans=(ans+(sum[j]-sum[i-1])%mod*(n/i)%mod*(m/i)%mod)%mod;
        }
        cout<<ans%mod<<endl;
    }
}