#include <cstdio>
typedef long long ll;

const ll MOD = 1e9 + 7;

ll kasumi(ll x, ll y) {
  ll res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}

ll gcd(ll x, ll y) {
  return y == 0 ? x : gcd(y, x % y);
}

int T;
int n, m;
ll k;
ll ans;

int main() {
  freopen("bzoj_4407.in", "r", stdin);
  freopen("bzoj_4407.out", "w", stdout);
  scanf("%d %lld", &T, &k);
  while (T--) {
    ans = 0;
    scanf("%d %d", &n ,&m);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        ans += kasumi(gcd(i, j), k) % MOD;
        ans %= MOD;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}