#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 70;
const int mod = 1e9 + 7;
typedef long long ll;
int t, k, tot, a[maxn], b[maxn], f[maxn][2][2][2][2];
ll n, m;
int s1(int n) {return ((ll)n * (n + 1) >> 1) % mod;}
int f1(int x, int y) {return ((ll)y * min(x, y - 1) - s1(min(x, y - 1))) % mod;}
int f2(int x, int y) {return ((ll)x * y - f1(x, y) - min(x, y)) % mod;}
void ckadd(int& a, int b) {a += b; if (a >= mod) a -= mod;}
int solve(int K, bool B, bool D, bool T1, bool T2) {
	if (!K) return B;
	int& res = f[K][B][D][T1][T2];
	if (~res) return res; res = 0;
	int x = T1 ? k - 1 : a[K], y = T2 ? k - 1 : b[K];
	if (x < y) {
		if (y - x - 1 > 0) res = (res + (ll)(y - x - 1) * solve(K - 1, 1, D, 1, T2)) % mod;
		if (min(x, y) - 1 > 0) res = (res + (ll)(min(x, y) - 1) * solve(K - 1, 1, D, T1, 1)) % mod;
		if (f1(x - 1, y - 1) > 0) res = (res + (ll)f1(x - 1, y - 1) * solve(K - 1, 1, D, T1, T2)) % mod;
		if (x < y) ckadd(res, solve(K - 1, 1, D, T1, T2));
	} else if (x == y) {
		if (x - 1 > 0) res = (res + (ll)(x - 1) * solve(K - 1, B, 1, T1, T2)) % mod;
		ckadd(res, solve(K - 1, B, 1, 1, 1));
	} else {
		if (min(x, y) - 1 > 0) res = (res + (ll)(min(x, y) - 1) * solve(K - 1, B, D, 1, T2)) % mod;
		if (x - y - 1 > 0) res = (res + (ll)(x - y - 1) * solve(K - 1, B, D, T1, 1)) % mod;
		if (f2(x - 1, y - 1) > 0) res = (res + (ll)f2(x - 1, y - 1) * solve(K - 1, B, D, T1, T2)) % mod;
		if (x > y) ckadd(res, solve(K - 1, B, D, T1, T2));
	} return res;
}
int main() {
    ios::sync_with_stdio(false);
	cin >> t >> k;
	while (t--) {
		cin >> n >> m; m = min(n, m); memset(f, -1, sizeof(f)); tot = 0;
		for (; n; n /= k, m /= k) a[++tot] = n % k, b[tot] = m % k;
		cout << solve(tot, 0, 0, 0, 0) << '\n';
	}
	return 0;
}