闲话
所以 cd 为啥突然学 gf
然后整出来一大堆奇怪的（初学者可能会有的）问题
建议来问我（
我还能乐呵乐呵（
EI：那你以后要知道这不奇怪
EI：小学生在初学负数时也会有疑惑
今日推歌：REWRITER - 八王子P feat. GUMI
杂题
我担心今天只有这一道了（
一个非负整数序列 \(S\) 是好的，当且仅当 \(S\) 存在一个非空子序列 \(T\)，满足 \(T\) 中所有元素的异或和为 \(1\)。
有一个初始为空的序列 \(A\)，以及 \(2^m\) 张写着数字的卡片；卡片上的数字取遍 \([0, 2^m)\) 中的整数。你可以自由选择一张卡片，将这张卡片上的数字放在 \(A\) 序列的末尾，并删除这张卡片，以后不能再选择它。你会一直进行这个操作，当 \(A\) 成为好的序列后停止。
给定 \(n, m\)，求停止操作时长度为 \(n\) 的不同 \(A\) 序列数。答案对 \(998244353\) 取模。
\(1\le n\le 2\times 10^5, \ 1\le m \le 10^7,\ n\le 2^m\)。
想装b 去选金牌题做 然后发现哪个都不可做就跑路了 找了个这个题
增加水题提交数（
前置知识。
题目中的生成方式等价于钦定序列 \(S\) 中数字互异。
设 \(A_n\) 是长度为 \(n\) 的好序列数量（数字不必两两不同），则答案即为 \(A_n - A_{n - 1} \times (2^m - n + 1)\)。这转化使我们可以简单容斥，用长度为 \(n\) 的序列总数减去数字互异的坏序列数就是答案。下面只需要计算数字互异的坏序列数即可。
设 \(f(n)\) 为数字互异的坏序列数，\(g(n)\) 为坏序列数。由于数字顺序对性质无影响，我们可以取一个数字互异的坏序列，将其中第 \(i\) 个元素扩增 \(k_i\ge 1\) 倍得到一个一般的坏序列。可以将每个数字看做一个盒子，第 \(i\) 个盒子中放 \(k_i\) 个球。这的组合意义自然导出了如下公式：
\]
斯特林反演得到
\]
我们已经充分了解了如何 \(O(n\log n)\) 求得一行斯特林数，下面只需要求得每个 \(g(k)\) 即可。这问题即为 CF1603F 当 \(x > 0\) 时的情况。我们已经知道了
g(k) &= \sum_{r=0}^k\prod_{i=1}^r(2^m-2^i) \begin{bmatrix} k \\ r \end{bmatrix}_2
\\ & = \sum_{r=0}^k 2^{r (r + 1) / 2} [m - 1]_2^{\underline {r - 1}} \begin{bmatrix} k \\ r \end{bmatrix}_2
\\ & = \sum_{r=0}^k 2^{r (r + 1) / 2} \frac{[m - 1]_2!}{[m - 1 - r]_2!} \begin{bmatrix} k \\ r \end{bmatrix}_2
\\ & = [m - 1]_2! [k]_2!\sum_{r=0}^k \left( \frac{2^{r (r + 1) / 2}}{[m - 1 - r]_2![r]_2! }\right)\left( \frac{1}{[k - r]_2!} \right)
\end{aligned}\]
一次卷积即可。
总时间复杂度为 \(O(n\log n + m)\)，需要预处理 \(\text{q-}\)阶乘和它的逆元。
