#include <bits/stdc++.h>
using namespace std;
int t,k,n,m,ans;
const int mod=1000000007;
int main(){
    freopen("bzoj_4407.in","r",stdin);
    freopen("bzoj_4407.out","w",stdout);    
    cin>>t>>k;
    while(t--){
        ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int a=__gcd(i,j);
                ans=(ans+pow(a,k));
                ans%=mod;
            }
        }
        cout<<ans<<"\n";
    } 
    
    return 0;
}