#include <bits/stdc++.h>
using namespace std;
#define ms(x, t) memset(x, t, sizeof(x))
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pll> vpll;
typedef vector<plll> vplll;
#define ff first
#define ss second
#define all(ar) ar.begin(), ar.end()
#define rall(ar) ar.rbegin(), ar.rend()
#define mp make_pair
#define pb push_back
#define pf push_front
#define endl "\n"
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a, b)                                                           \
  cerr << #a << ": " << a << " | " << #b << ": " << b << endl;
#define trace3(a, b, c)                                                        \
  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": "   \
       << c << endl;

const int limit = 1e5 + 1;
const int inf = 1e7;
const int mod = 1e9 + 7;

vector<vl> matI(int n) {
  vector<vl> I(n, vl(n, 0));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j)
        I[i][j] = 1;
    }
  }
  return I;
}

vector<vl> matMul(vector<vl> &a, vector<vl> &b) {
  ll n = a.size();
  ll m = b[0].size();
  ll l = b.size();
  vector<vl> c(n, vl(m, 0));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < l; k++) {
        c[i][j] = (c[i][j] + (a[i][k] % mod * b[k][j] % mod) % mod) % mod;
      }
    }
  }

  return c;
}

vector<vl> matExp(ll n, vector<vl> &a) {
  int m = a.size();
  vector<vl> ans = matI(m);

  while (n) {
    if (n & 1) {
      ans = matMul(a, ans);
    }
    a = matMul(a, a);
    n = n >> 1;
  }
  return ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll t;
  cin >> t;
  while (t--) {
    ll n, m;
    cin >> n >> m;

    vector<vl> p = {{m - 1, m - 1}, {1, 0}};
    vector<vl> a = {{m}, {0}};
    vector<vl> e = matExp(n - 1, p);
    vector<vl> res = matMul(e, a);
    cout << (res[0][0] + res[1][0]) % mod << endl;
  }

  return 0;
}