先把存在性容斥一下。变成 \([0,\infty]\) 减去 \([0,x-1]\) 和 \([x+k,\infty]\)。
\([0,x-1]\) 的答案显然可以矩阵快速幂 \(\mathcal O(x^3\log n)\) 求。考虑剩下两个。注意到两个单拎出来都不好求，所以直接求这两个的差。
注意到限制在于相邻项的差，于是我们去枚举差分数组，共有 \((2k+1)^{n-1}\) 种，然后考虑第一项，具体推导可以看八云蓝的题解，感性理解一下就是，\(p\) 在 \([0,\infty]\) 中的地位和 \(p+x+k\) 在 \([x+k,\infty]\) 中的地位是一样的，于是两者之差只有 \(x+k\) 项，于是答案就是 \((x+k)(2k+1)^{n-1}\)。时间复杂度 \(\mathcal O(Tx^3\log n)\)。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using i64 = long long;
using pii = std::pair<int, int>;
constexpr int maxn = 40 + 5;
constexpr int mod = 1e9 + 7;
void add(int& x, int y) { if ((x += y) >= mod) x -= mod; return ; }
void sub(int& x, int y) { if ((x -= y) < 0) x += mod; return ; }
int inc(int x, int y) { return (x + y) >= mod ? (x + y - mod) : (x + y); }
int dec(int x, int y) { return (x - y) < 0 ? (x - y + mod) : (x - y); }
int power(int x, int y) {
int ans = 1;
for (; y; y >>= 1, x = (i64)x * x % mod) if (y & 1) ans = (i64)ans * x % mod;
return ans;
}
void chkmin(int& x, int y) { if (y < x) x = y; return ; }
void chkmax(int& x, int y) { if (y > x) x = y; return ; }
void chkmin(i64& x, i64 y) { if (y < x) x = y; return ; }
void chkmax(i64& x, i64 y) { if (y > x) x = y; return ; }
int n, k, x;
struct matrix {
int g[maxn][maxn];
matrix() { memset(g, 0, sizeof(g)); }
void clr() { memset(g, 0, sizeof(g)); return ; }
void init() { for (int i = 0; i < x; ++i) g[i][i] = 1; return ; }
matrix operator * (const matrix& p) const {
matrix z;
for (int i = 0; i < x; ++i)
for (int k = 0; k < x; ++k)
for (int j = 0; j < x; ++j)
add(z.g[i][j], (i64)g[i][k] * p.g[k][j] % mod);
return z;
}
} F, G;
matrix power(matrix x, int y) {
matrix ans; ans.init();
for (; y; y >>= 1) {
if (y & 1) ans = ans * x;
x = x * x;
}
return ans;
}
void work() {
scanf("%d %d %d", &n, &x, &k);
int ans = (i64)(x + k) * power(2 * k + 1, n - 1) % mod;
F.clr(); G.clr();
for (int i = 0; i < x; ++i)
F.g[0][i] = 1;
for (int i = 0; i < x; ++i)
for (int j = 0; j < x; ++j)
if (abs(i - j) <= k) G.g[i][j] = 1;
F = F * power(G, n - 1);
for (int i = 0; i < x; ++i)
sub(ans, F.g[0][i]);
printf("%d\n", ans);
return ;
}
int main() {
int T; scanf("%d", &T);
while (T--) work();
return 0;
}