#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1000000007;
ll n,m,k,T;
ll read(){
	ll x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll ksm(ll a,ll b){
	ll ans=1,base=a;
	while(b){
		if(b&1){
			ans*=base;
			ans%=mod;
		}
		base*=base;
		base%=mod;
		b>>=1;
	}
	return ans%mod;
}
ll ans,t;
int main(){
	freopen("bzoj_4407.in","r",stdin);
	freopen("bzoj_4407.out","w",stdout);
	T=read();k=read();
	while(T--){
		n=read();
		m=read();
		ans=0;
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=m;j++){
				t=gcd(i,j);
				t=ksm(t,k);
				ans+=t;
				ans%=mod;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}