对于一个定长(size = n)的数列a, 若其存在“位置相关”的子集（含空集）使得该子集所有元素之和为k，那么将数列a计数。
其中数列a中任一元素a[i]在[0, l]内*取值。
数据条件0≤n, k ≤ 20, 0≤ l ≤ 1e9,计数结果对mod = 1e9 + 7取模。
无论直接计数还是考虑从反面计数都解决不了去重的问题，只能考虑dp。
枚举数列的长度i和压缩后的状态j，并且记录在该条件下的数列选取方案数dp[i][j]。
压缩后的状态j表示对于集合{1, 2, ..., min(l, k)}的选取情况。
其中集合中第i个元素在状态j中当且仅当j的二进制串的第i位为1。
显然我们有dp[0][0] = 1。
对于长度为p的数组，第p位可以选取的元素是0,1,2，...，l
考虑p位选取1,2，...，min(l, k)
那么对于数组长度为p-1时的任一状态j，在数组后追加元素i后的状态为：
j1 = j | ((j << i) & ((1 << k) - 1)) | (1 << (i - 1))
三部分分别表示原状态，原状态每个元素与元素i求和后增加的状态，i本身。
于是dp[p][j1] += dp[p - 1][j]。
而对于p位选取0或者大于min(l, k)的情形，j1 = j。
因此有dp[p][j] = (l - min(l, k)) * dp[p - 1][j]。
我们最后只需对dp[n][j]，其中j第k位为1的累加即可。
由于数列每个元素非负，我们最后只关心那些集合存在和为k的子集，
而那些大于k的元素必然不是构成子集的元素，只有那些小于k的元素才对状态转移有用。
因此我们可以这样表示状态。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <ctime>
using namespace std;
#define lson (u << 1)
#define rson (u << 1 | 1)
typedef __int64 ll;
const int maxn = 1e6 + ;
const int maxm = ;
const ll mod = 1e9 + ; int n, l, k;
ll dp[( << ) + ];
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &k, &l);
ll d = abs(l - k);
l = min(l, k);
int s = ( << k) - ;
memset(dp, , sizeof dp);
dp[] = ;
while(n--){
for(int j = s; j >= ; j--){
ll tem = dp[j];
if(!tem) continue;
for(int p = ; p <= l; p++){
int nex = ( << (p - )) | j | ((j << p) & s);
dp[nex] = (dp[nex] + tem) % mod;
}
dp[j] = (tem * ( + d)) % mod;
}
}
ll ans = ;
for(int i = s; i >= ; i--)
if(i & ( << (k - )))
ans = (ans + dp[i]) % mod;
printf("%I64d\n",ans);
}
return ;
}