#include <iostream>
using namespace std;
long long T,k,n,m,ans;
long long mod=1000000007;
inline long long qpow(long long a, long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1)(res*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return res;
}
inline long long gcd(long long a, long long  b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
int main()
{
    freopen("bzoj_4407.in","r",stdin);
    freopen("bzoj_4407.out","w",stdout);
    cin>>T>>k;
    while(T--)
    {
        cin>>n>>m;
        for(long long i=1;i<=n;i++)
        for(long long j=1;j<=m;j++)
        {
            ans+=qpow(gcd(i,j),k);
        }
    }
    cout<<ans;
    return 0;
}