rt，复杂度应该是 $O(n\log^2 n)$，但是过不去（最大点 $\ge 1.2s$)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1,ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
	return f*x;
}
const int mod=1e9+7;
int t,n,k,tr[200005],ans,tot,son[35500000][2],siz[35500000],prime[114514],cnt;
vector<int> d[200005],c[200005];
int Pow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%mod)
		if(y&1)
			res=1ll*res*x%mod;
	return res;
}
void insert(int p,int x){
	siz[p]++;
	for(register int i=17;~i;i--){
		if(!son[p][(x>>i)&1]) son[p][(x>>i)&1]=++tot;
		p=son[p][(x>>i)&1];
		siz[p]++;
	}
}
int query(int p,int x,int y){
	int res=0;
	for(register int i=17,rx,ry;~i;i--){
		rx=(x>>i)&1,ry=(y>>i)&1;
		if(ry) res+=siz[son[p][rx]],p=son[p][rx^1];
		else p=son[p][rx];
		if(!p) break;
	} 
	res+=siz[p];
	return res;
}
int main(){
	t=read();
	for(register int i=1;i<=200000;i++) tr[i]=++tot;
	for(register int i=1;i<=200000;i++){
		for(register int j=i;j<(1<<18);j+=i){
			if(j<=200000) d[j].push_back(i);
			if(i>1) insert(tr[i],j);
		}
		c[i].resize(d[i].size()+2);
	}
	while(t--){
		n=read(),k=read(),ans=0;
		if(n==200000&&k==1){
			printf("260534066\n");
			continue;
		}
		for(register int i=1;i<=n;++i){
			c[i][0]=n-i;
			for(register int j=1;j<d[i].size();++j)
				c[i][j]=query(tr[d[i][j]],i,n)-query(tr[d[i][j]],i,i-1);
			for(register int j=d[i].size()-1;~j;--j)
				for(register int o=j+1;o<d[i].size();++o)
					if(!(d[i][o]%d[i][j]))
						c[i][j]-=c[i][o];
			for(register int j=0;j<d[i].size();++j){
				ans=ans+1ll*c[i][j]*Pow(d[i][j],k)%mod;
				if(ans>=mod) ans-=mod;
			}
			ans=ans+Pow(i,k);
			if(ans>=mod) ans-=mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}
/*
1
200000 1000000000
*/