首篇题解。
双倍经验。

$\binom{i}{j} \bmod k = 0$ 相当于在 $p$ 进制下至少有一位 $n_i \lt m_i$。
正难则反，考虑先求出对于所有位 $n_i \geq m_i$ 的答案，再容斥。

注意位与位之间的大小关系是独立的，只需要知道每一位内部 $n_i,m_i$ 的大小关系即可。
这很像一个数位 DP。

设 $f_{i,0/1,0/1}$ 表示 DP 到 $p$ 进制下第 $i$ 位，$n$ 顶上界情况为 $0/1$，$m$ 顶上界情况为 $0/1$，满足 $n_i \geq m_i$ 的方案数为多少。
并不难发现可以 $O(k^2 \log_k n)$ 转移，即暴力枚举 $n,m$ 这一位填什么。
然而事实上不需要枚举填什么，只需要知道方案数就行了。
考虑设一个函数 cnt(l,r) 表示 $i \in [0,l], j \in [0,r]$，计算 $i \geq j$ 的方案数。
那么转移只需要枚举 $n,m$ 各自顶不顶这一位上界即可。

• 如果两者都要顶上界，那只有一种填法，特判即可。

$$f_{i,1,1} \times [n_{i-1} \geq m_{i-1}] \to f_{i-1,1,1}$$

• 如果只有 $n$ 顶上界，只需考虑 $m$ 上一次有没有顶上界即可。
• 注意是 $m_{i-1}$ 而非 $m_{i-1}+1$，因为 $m_{i-1}$ 不能填，填了就变成 $f_{i,1,1}$ 了。

$$f_{i,1,0} \times (n_{i-1}+1) + f_{i,1,1} \times \min(n_{i-1}+1,m_{i-1}) \to f_{i-1,1,0}$$

• 如果只有 $m$ 顶上界，只需考虑 $n$ 上一次有没有顶上界即可。

$$f_{i,0,1} \times (k-m_{i-1}) + f_{i,1,1} \times \max(0, n_{i-1} - m_{i-1}) \to f_{i-1,0,1}$$

• 如果都不顶上界，那四种情况都可以转移而来：

$$f_{i,1,1} \times cnt(n_{i-1},m_{i-1}) + f_{i,1,0} \times cnt(n_{i-1},k) + f_{i,0,1} \times cnt(k,m_{i-1}) + f_{i,0,0} \times cnt(k,k)$$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;

inline int cnt(int l, int r) {   // 求 i<-[0,l]  j<-[0,r] 且 i >= j 的方案数
    if (l <= r) {
        l %= mod, r %= mod;
        return (l * (l + 1) / 2ll) % mod;
    }
    l %= mod, r %= mod;
    return ( (r * (r + 1) / 2ll) % mod + (l - r) * r % mod ) % mod;
}

int N, M, x, ans;
int n[70], m[70], totn, totm, T, k;
int f[70][2][2];
void DP() {
    f[max(totn, totm)][1][1] = 1;
    for (int i = max(totn, totm); i >= 1; i--) {
        if (n[i - 1] >= m[i - 1]) f[i - 1][1][1] = f[i][1][1];
        f[i - 1][1][0] = f[i][1][0] * (n[i - 1] + 1) % mod + f[i][1][1] * min(  n[i - 1] + 1, m[i - 1]) % mod;
        f[i - 1][0][1] = f[i][0][1] * (k - m[i - 1]) % mod + f[i][1][1] * max(0ll, n[i - 1] - m[i - 1]) % mod;
        f[i - 1][0][0] = f[i][1][1] * cnt(n[i - 1], m[i - 1]) % mod + f[i][1][0] * cnt(n[i - 1], k) % mod + f[i][0][1] * cnt(k, m[i - 1]) % mod + f[i][0][0] * cnt(k, k) % mod;
        for (int j = 0; j < 2; j++)
            for (int l = 0; l < 2; l++) f[i - 1][j][l] %= mod;
    }
}

void solve() {
    for (int i = 0; i <= 65; i++) {
        n[i] = m[i] = 0;
        for (int j = 0; j < 2; j++) for (int l = 0; l < 2; l++) f[i][j][l] = 0;
    }
    scanf("%lld%lld", &N, &M), M = min(N, M);
    totn = 0, x = N; while (x) n[totn++] = x % k, x /= k;
    totm = 0, x = M; while (x) m[totm++] = x % k, x /= k;
    DP();
    ans = cnt(N + 1, M + 1) - f[0][1][1] - f[0][1][0] - f[0][0][1] - f[0][0][0];
    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
}

signed main() {
    scanf("%lld%lld", &T, &k);
    while (T--) solve();
    return 0;
}