为什么会是 *2700？？？
首先考虑一下 \(x\) 的作用是什么，感受一下，会感觉 \(0\) 或许会比较特殊（如果做点线性基的题能感受到）。
首先考虑 \(x = 0\)，这就相当于要求 \(n\) 个 \([0, 2^k)\) 元素满秩的方案数，考虑类似线性基，依次加入元素，那么加入第 \(i\) 个元素时就不能被前 \(i - 1\) 个元素线性表示，所以方案数是 \(\prod\limits_{i = 1}^n (2^k - 2^{i - 1})\)。
因为 \(n\le k\) 时才可能放不出 \(0\)，所以 \(n > k\) 时答案为 \(0\)，\(n\le k\) 时 \(\mathcal{O}(k)\) 计算。
接下来考虑 \(x\not = 0\) 的情况，会发现 \(x\not = 0\) 的答案是相同的（我并不知道怎么解释，但是从后面的做法中可以看出来这一点）。
对于不能凑出 \(x\)，一个想法是放入 \(x\) 变为不能凑出 \(0\)。
于是对于 \(a_i\)，根据 \(a_{1\sim i - 1}\) 和 \(x\) 就有两种情况：
- \(a_i\) 能被 \(a_{1\sim i - 1}\) 线性表示。
- \(a_i\) 不能被 \(x\) 及 \(a_{1\sim i - 1}\) 线性表示。
（其实就是 \(a_i\) 不能被 \(x\) 和 \(a_{1\sim i - 1}\) 的部分线性表示的转义。）
于是可以尝试 dp，记 \(f_{i, j}\) 为放入了 \(a_{1\sim i}\)，秩为 \(j\) 的方案数。
转移根据上文可以得到 \(f_{i, j} = f_{i - 1, j}\times 2^{j - 1} + f_{i - 1, j - 1}\times (2^k - 2^{j - 1})\)。
初值即为 \(f_{0, 1} = 1\)，最终答案为 \(\sum_{i = 0}^k f_{n, i}\)。
因为答案所要求的第一维都是 \(n\)，尝试枚举第二维然后代数推导，即考虑代数推导 \(f_{n, i}\) 的值。
考虑转移的第二部分，即第二维 \(+1\) 时乘上的值都是 \((2^k - 2_{j - 1})\)，那么 \(f_{n, i}\) 就至少有一个 \(\prod\limits_{j = 2}^i (2^k - 2^{j - 1})\) 的公因式，就只需要考虑第一部分的贡献和两部分拼起来的贡献了。
此时考虑直接枚举每个 \(j\) 乘了多少个 \(2^{j - 1}\)，会发现这恰好也数出了组合的方案数，因为整个过程是有序的，所以可以直接通过乘了多少个 \(2^{j - 1}\) 推出每次 \(j\gets j + 1\) 的位置。
所以有：
后面这个和式只能尝试转为生成函数推导：
\(F_i(x)\) 的求解似乎不能用分式分解（我尝试了，没化出来 qaq），考虑观察 \(x\)，发现前面都带有 \(2^{j - 1}x\) 的系数，这启发对 \(x\) 前配凑系数：
那么可以知道：
于是对第二个式子两侧取 \([x^m]\) 可以得到：
通过边界情况 \([x^0]F_i(x) = 1\) 便可得到：
所以：
但是我们想要做到 \(\mathcal{O}(k)\)，于是尝试找一些递推关系，可以发现：
递推要做到 \(\mathcal{O}(1)\)，就需要先 \(\mathcal{O}(\log \operatorname{mod})\) 得到 \(2^{n + 0\sim 1}\)（看实现），每次乘 \(\frac{1}{2}\)，分母逆元我用的是 \(\mathcal{O}(n + \log \operatorname{mod})\) 处理任意序列 \(a_{1\sim n}\) 的逆元的方法。
最后总时间复杂度为 \(\mathcal{O}(\sum k + T\log \operatorname{mod})\)。
#include <bits/stdc++.h>using ll = long long;constexpr ll mod = 998244353;
constexpr ll inv2 = 499122177;constexpr int K = 1e7;inline ll qpow(ll a, ll b) {ll v = 1;for (; b; b >>= 1, a = a * a % mod) {if (b & 1) {v = v * a % mod;}}return v;
}ll pw[K + 1], inv[K + 1];
ll a[K + 1], b[K + 1], ib[K + 1];
inline void init() {pw[0] = 1;for (int i = 1; i <= K; i++) {pw[i] = pw[i - 1] * 2 % mod;}b[0] = 1;for (int i = 1; i <= K; i++) {a[i] = pw[i] - 1;b[i] = b[i - 1] * a[i] % mod;}ib[K] = qpow(b[K], mod - 2);for (int i = K; i >= 1; i--) {ib[i - 1] = ib[i] * a[i] % mod;inv[i] = b[i - 1] * ib[i] % mod;}
}inline void solve() {int n, k, x;scanf("%d%d%d", &n, &k, &x);if (x == 0) {if (n > k) {return puts("0"), void();}ll ans = 1;for (int i = 1; i <= n; i++) {ans = ans * (pw[k] - pw[i - 1] + mod) % mod;}return printf("%lld\n", ans), void();}ll ans = 0, v1 = 1, v2 = 1, pwi = qpow(2, n + 1);for (int i = 1; i <= std::min(n + 1, k); i++) {if (i >= 2) {v1 = v1 * (pw[k] - pw[i - 1] + mod) % mod;pwi = pwi * inv2 % mod;v2 = v2 * inv[i - 1] % mod * (pwi - 1) % mod;}ans = (ans + v1 * v2) % mod;}printf("%lld\n", ans);
}int main() {init();int t;scanf("%d", &t);while (t--) {solve();}return 0;
}