看了一下之前的提交记录，大部分都是锐角三角形 15pts.

RT. 主要我现在没有条件调。

#include <iostream>
using namespace std;
__int128 k, dp[105][2][2], a[105], b[105]; bool vis[105][2][2];
__int128 rd() {long long qwq; cin >> qwq; return qwq;}
__int128 dfs(__int128 cur, __int128 lma, __int128 lmb) {
if (!cur) return 1; if (vis[cur][lma][lmb]) return dp[cur][lma][lmb];
__int128 summ = 0;
for (int i=0; i<min(k, lma? a[cur] + 1: 0x3fffffff); i++) for (int j=0; j<=min((__int128)i, lmb? b[cur]: 0x3fffffff); j++) (summ += dfs(cur-1, lma && i == a[cur], lmb && i == b[cur])) %= (__int128)1e9+7; return vis[cur][lma][lmb] = 1, dp[cur][lma][lmb] = summ;
}
int main() {
__int128 t, n, m, seele, x, y; t = rd(); k = rd();
while (t--) {seele = 0;
n = rd(); m = rd(); m = min(n, m); x = n; y = m; while (n) {a[++seele] = n % k; n /= k; b[seele] = m % k; m /= k;} for (int i=1; i<=seele; i++) vis[i][0][0] = vis[i][0][1] = vis[i][1][0] = vis[i][1][1] = 0;
cout << (long long)((((y + 1) * (y + 2) / 2 % (__int128)(1e9+7) + (x - y + (__int128)(1e9+7)) * (y + 1) % (__int128)(1e9+7)) - dfs(seele, 1, 1) + (__int128)(1e9+7)) % (__int128)(1e9+7)) << endl;
}
}