#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
ll t,n,m,k;
ll gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
ll ksm(ll a,ll b,ll p){
	ll res=1;
	for(;b;b>>=1,a=a*a%p) res=res*(b&1?a:1)%p;
	return res;
}
int main(){
	freopen("bzoj_4407.in","r",stdin);
	freopen("bzoj_4407.out","w",stdout);
	scanf("%lld%lld",&t,&k);
	while(t--){
		ll ans=0;
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				ans=(ans+ksm(gcd(i,j),k,mod))%mod;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}