1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define pb push_back
using namespace std;
const int N = 70, mod = 1e9 + 7, inv2 = 5e8 + 4;
typedef long long L;
typedef vector <int> VI;
L n, m;
VI a, b;
int k, f[N][2][2];
int dfs (int t, bool p, bool q)
{
if (!~t) return 1;
if (~f[t][p][q]) return f[t][p][q];
int x = p ? a[t] : k - 1, y = q ? b[t] : k - 1, res = 0;
for (int i = 0; i <= x; ++i)
for (int j = 0; j <= i && j <= y; ++j)
res = (res + dfs(t - 1, p && i == x, q && j == y)) % mod;
return f[t][p][q] = res;
}
int main ()
{
int T; cin >> T >> k;
while (T--)
{
cin >> n >> m; m = min(n, m);
a.clear(), b.clear();
int res = ((m + 1) % mod * ((m + 2) % mod) % mod * inv2 + (m + 1) % mod * ((n - m) % mod)) % mod;
for (; n; n /= k) a.pb(n % k);
for (; m; m /= k) b.pb(m % k);
b.resize(a.size(), 0);
memset(f, -1, sizeof f);
cout << (res - dfs(a.size() - 1, 1, 1) + mod) % mod << endl;
}
}
|