首先来考虑 Easy。
注意到的是最后输出的答案要求是模意义下的，这说明对于实数二分的做法都已经用不了了。
注意到 \(n, m\le 3000\) 的数据范围，于是一个想法就是考虑 DP 之类的算法。
考虑到 B 选了 \(+ / -\) 实际上就代表着下一轮的 \(m\) 是否会 \(-1\)，于是可以设状态为 \(f_{i, j}\) 表示还有 \(i\) 轮，还有 \(j\) 个 \(+\) 要选的最优值。
那么边界值容易知道是 \(f_{i, 0} = 0, f_{i, i} = ik\)，即如果只剩 \(-\) 那么肯定是 A 全选 \(0\)，如果全剩 \(+\) 那么肯定是 A 全选 \(k\)。
那么就来考虑 \(f_{i, j}(j\in (0, i))\) 的转移，考虑到 A 选了一个 \(x\) 后，B 会选 \(+ / -\)，因为 B 想最小，于是 B 选出来的一定是 \(\min\{f_{i - 1, j - 1} + x, f_{i - 1, j} - x\}\)。
因为 A 要最大化，相当于是 \(f_{i, j} = \max\{\min\{f_{i - 1, j - 1} + x, f_{i - 1, j} - x\}\}(x\in [0, k])\)。
于是从函数图象分析，非常显然的是肯定是取 \(x = \frac{f_{i - 1, j} - f_{i - 1, j - 1}}{2}\) 最优，此时有 \(f_{i, j} = \frac{f_{i - 1, j - 1} + f_{i - 1, j}}{2}\)。
其实上面还漏了一步，为什么这个 \(x\) 一定能被选出来？
那么实际上就是说明 \(f_{i - 1, j} - f_{i - 1, j - 1}\le 2k\)，这个还是比较显然的，因为再劣也劣不过把 \(-k\) 改为 \(+k\) 的 \(\Delta = 2k\)。
于是 Easy 就做完了，时间复杂度 \(\mathcal{O}(nm)\)。
接下来考虑 Hard。
那么一个想法是 DP 转移的值实际上都是有 \(f_{i, i}\) 的边界条件推来的，于是可以对于每个 \((i, i)\) 单独统计对 \((n, m)\) 的贡献。
首先考虑到的是 DP 中从 \(i\to i + 1\) 就会有 \(\frac{1}{2}\) 的系数，所以首先就有个 \(\frac{1}{2^{n - i}}\) 的系数。
其次考虑到 \((i, i)\) 剩下时候就可以任意走 \((+1, +1)\) 或者 \((+1, 0)\)，但是不能走到 \((j, j)\)。
但是发现不能走到 \((j, j)\) 是好算的，因这个的充要条件就是走到了 \((i + 1, i + 1)\)。
于是只需要钦定第一步走到是 \((+1, 0)\) 就可以了，方案数为 \(\binom{n - i - 1}{m - i}\)。
于是就在 \(\mathcal{O}(n)\) 的时间复杂度做完了。
注意特判 \(n = m\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7, inv2 = mod + 1 >> 1;
inline ll qpow(ll a, ll b, ll v = 1) {
while (b)
b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod;
return v;
}
const int maxn = 1e6 + 10, N = 1e6;
ll fac[maxn], ifac[maxn], pw[maxn];
inline void init() {
for (int i = fac[0] = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N; i; i--) ifac[i - 1] = ifac[i] * i % mod;
for (int i = pw[0] = 1; i <= N; i++) pw[i] = pw[i - 1] * inv2 % mod;
}
inline ll binom(int n, int m) {return fac[n] * ifac[m] % mod * ifac[n - m] % mod;}
inline void solve() {
int n, m; ll k; scanf("%d%d%lld", &n, &m, &k);
if (n == m) return printf("%lld\n", m * k % mod), void();
ll ans = 0;
for (int i = 1; i <= m; i++)
(ans += 1ll * i * k % mod * binom(n - i - 1, m - i) % mod * pw[n - i]) %= mod;
printf("%lld\n", ans);
}
int main() {
init();
int T; scanf("%d", &T);
for (int id = 1; id <= T; id++) solve();
return 0;
}