#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 3e18;
const ll MOD = 1e9 + 7;
int T, k, K;
ll n, m, powk[65];
ll f[65][2][2];

ll dfs(int len, bool lim1, bool lim2) {
	if (len == 0) return 1;
	if (~f[len][lim1][lim2]) return f[len][lim1][lim2];
	int up = lim1 ? n / powk[len - 1] % k : k - 1, uq = lim2 ? m / powk[len - 1] % k : k - 1;
	ll res = 0;
	for (int i = 0; i <= up; i++)
		for (int j = 0; j <= i && j <= uq; j++)
			res = (res + dfs(len - 1, lim1 && i == up, lim2 && j == uq)) % MOD;
	return f[len][lim1][lim2] = res;
}

int main() {
	scanf("%d%d", &T, &k);
	powk[0] = 1;
	for (K = 1; INF / powk[K - 1] >= K; K++) powk[K] = powk[K - 1] * k; 
	while (T--) {
		scanf("%lld%lld", &n, &m);
		memset(f, -1, sizeof f);
		m = min(n, m);
		printf("%lld\n", (((2 + m) % MOD * ((m + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD
		  + (n - m) % MOD * ((m + 1) % MOD) % MOD
		  - dfs(K, true, true)) % MOD + MOD) % MOD);
	}
	return 0;
}