题意
有 T 次询问，一开始给定一个 k，之后每次询问给定 n,m，求 ∑nx=1∑y=0min 的值。
1 \le T \le 10^5,1 \le k \le 10^8, 1 \le n,m \le 10^{18}。
分析
直接做是难做的，但是我们考虑到有 C_x^y \bmod k 的形式，考虑用 \text{Lucas} 定理。
C_x^y \bmod k= C_{ \bmod k}^{y \bmod k} \times C_{\left \lfloor x/k \right \rfloor}^{\left \lfloor y/k \right \rfloor}
因为要求 C_x^y \bmod k = 0，所以一定是 C_{x \bmod k}^{y \bmod k}，因为如果只有 x<y，C_x^y 才会等于 0。
于是我们可以对 x,y 按照 k 进制拆分。假设 x 的 k 进制拆分的第 i 为是 a_i，y 的 k 进制拆分的第 i 位是 b_i。其中 a_0,b_0 是最低位。
于是我们就知道，只要让 \exists i,a_i < b_i，就会使得 C_x^y \bmod k = 0。存在是困难的，正难则反，去计算 \forall i,a_i \le b_i 的方案数，用总的方案数减去。
定义 f_{i,0/1,0/1} 表示考虑到第 i 为，x 是否顶到上界，y 是否顶到上界。
首先，如果 m>n，多出来的是无意义的，所以一开始 m \gets \min(n,m)。
然后就开始快乐推式子。
f_{i,1,1} \gets f_{i+1,1,1}[a_i\ge b_i]
如果两个数字都是上界，那么上一次一定是上界，并且这一次也是上界。所以只要考虑当前位的大小。
f_{i,1,0} \gets f_{i+1,1,1} \times \min(a_i + 1, b_i) + f_{i+1,1,0} \times (a_i + 1)
如果只有 x 顶到上界，说明上一位 x 也是上界，考虑 y 是否顶到上界。如果 y 上一位顶到了上界，那么这一位可以 y 选的数字同时受到 y \le x 和 y \le m 的限制，所以是 min(a_i+1,b_i)。
而如果上一次 y 没有顶到上界，这一位就只受到 y \le x 的限制。
f_{i,0,1} \gets f_{i+1,1,1} \times \max(b_i - a_i,0) + f_{i+1,0,1} \times (k-b_i)
如果只有 y 顶到上界，那么上一位 y 也是上界。如果 x 上一位是上界，那么 x 有一个 n 的上界和 x \ge y 的下界，所以有 \max(a_i - b_i,0) 中选择方法。
如果上一次没有顶到上界，那么没有了 n 的上界。所以有 k - b_i 种选法，毕竟 k 进制只能小于 k。
在推到 f_{i,0,0} 之前，我们先定义 G(n,m) 函数方便计算。
G(n,m) = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} [i \ge j]
其中可以证明如下结果。
G(n,m) =\left\{\begin{matrix}\frac{m(m+1)}{2}+(n-m)m \hspace{1cm}n \ge m\\ \frac{n(n+1)}{2} \hspace{4cm}n<m\end{matrix}\right.
首先证明上面式子是简单的。如果 n \ge m，那么写算 i,j 都不大于 m 的，再加上 i 大于 m，j 不大于 m。
如果 n < m，那么直接 m \gets \min(n,m)，再带入上式，得到新的结果。实际上代码实现可以直接 m \gets \min(n,m)，然后带上面的公式。
f_{i,0,0} \gets f_{i+1,1,1} \times G(a_i,b_i) + f_{i+1,1,0} \times G(a_i,k) + f_{i+1,0,1} \times G(k,b) + f_{i,0,0} \times G(k,k)
这个式子就是好推的，因为两个都无法确定，所以只要选择的数字满足 a_i \ge b_i 即可。当然，这一位的上界取决于上一位是否顶到了上界，所以系数是不一样的。
最后就是 O(T\log_k n) 的时间复杂度，带上一个 4 的常数。这里理论最差是 k = 2,O(T\log n)。
但是我们似乎忘了什么。我们求的是 \exists i,a_i < b_i，要用总的减去。总的方案数其实就是选择 x,y 使得 x \le y 的方案数，与 G 是一样的，直接用，但是注意写的时候要先取 \min 再模。
il int G(ll n, ll m){
m = min(n, m), n %= P, m %= P;
return ((1ll * m * (m + 1) % P * inv2 % P + 1ll * (n - m) * m % P) % P + P) % P;
}
因为 n,m 是 10^{18} 级别，直接乘起来会炸 \text{long long}，所以要取模。如果先取模，会影响大小关系。
最后就是真的结束了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
il ll rd(){
ll s = 0, w = 1;
char ch = getchar();
for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
return s * w;
}
const int P = 1e9 + 7, inv2 = 500000004;
int T, k, f[75][2][2], L, A[75], B[75];
ll n, m;
il void add(int &x, int y){x = ((x + y) % P + P) % P;}
il int G(ll n, ll m){
m = min(n, m), n %= P, m %= P;
return ((1ll * m * (m + 1) % P * inv2 % P + 1ll * (n - m) * m % P) % P + P) % P;
}
il int max(int a, int b){return (a > b) ? a : b;}
il int min(int a, int b){return (a < b) ? a : b;}
int Main(){
n = rd(), m = rd(), m = min(n, m);
memset (f, 0, sizeof f), memset (A, 0, sizeof A), memset (B, 0, sizeof B);
int i, j, ans = G(n + 1, m + 1);
for (i = 0; n; n /= k, i++) A[i] = n % k;
for (j = 0; m; m /= k, j++) B[j] = m % k;
L = max(i, j);
f[L + 1][1][1] = 1;
for (int i = L; i >= 0; i--){
int a = A[i], b = B[i];
if (a >= b) add(f[i][1][1], f[i + 1][1][1]);
add(f[i][1][0], 1ll * f[i + 1][1][1] * min(a + 1, b) % P), add(f[i][1][0], 1ll * f[i + 1][1][0] * (a + 1) % P);
add(f[i][0][1], 1ll * f[i + 1][1][1] * max(a - b, 0) % P), add(f[i][0][1], 1ll * f[i + 1][0][1] * (k - b) % P);
add(f[i][0][0], 1ll * f[i + 1][1][1] * G(a, b) % P), add(f[i][0][0], 1ll * f[i + 1][1][0] * G(a, k) % P);
add(f[i][0][0], 1ll * f[i + 1][0][1] * G(k, b) % P), add(f[i][0][0], 1ll * f[i + 1][0][0] * G(k, k) % P);
}
add(ans, -f[0][1][1]), add(ans, -f[0][1][0]), add(ans, -f[0][0][1]), add(ans, -f[0][0][0]);
printf ("%d\n", ans);
return 0;
}
int main(){
for (T = rd(), k = rd(); T--;) Main();
return 0;
}
