AT_arc139_f [ARC139F] Many Xor Optimization Problems

PCT 君出了一道如下题目。 > **Xor 优化问题** 给定一个长度为 $N$ 的非负整数序列 $A_1,A_2,\ldots,A_N$。你可以任选若干个 $A$ 的元素，所选元素的 $\mathrm{XOR}$ 能取得的最大值是多少？ 由于这道题对 Nyaan 君来说太简单了，PCT 君将题目改成了如下形式。 > **多个 Xor 优化问题** 长度为 $N$ 且所有元素都在 $0$ 到 $2^M-1$ 之间的整数序列共有 $2^{NM}$ 种。对于所有这些序列，分别求解 **Xor 优化问题**，将所有答案之和对 $998244353$ 取模，输出结果。 请你解决 **多个 Xor 优化问题**。 $\mathrm{XOR}$ 的定义如下： 对于非负整数 $A,B$，它们的按位 $\mathrm{XOR}$，记作 $A\oplus B$，定义为： - $A\oplus B$ 的二进制表示中 $2^k$（$k\geq 0$）位上的数，如果 $A,B$ 的二进制表示在 $2^k$ 位上只有一个为 $1$，则该位为 $1$，否则为 $0$。 例如，$3\oplus 5=6$（二进制表示为：$011\oplus 101=110$）。 一般地，$k$ 个非负整数 $p_1,p_2,\ldots,p_k$ 的按位 $\mathrm{XOR}$ 定义为 $(\cdots((p_1\oplus p_2)\oplus p_3)\oplus\cdots\oplus p_k)$，并且可以证明其结果与顺序无关。

输入从标准输入读入，格式如下： > $N$ $M$

请输出答案。

### 数据范围 - $1\leq N,M\leq 250000$ - 输入均为整数。 ### 样例解释 1 对于长度为 $2$ 且所有元素都在 $0$ 到 $1$ 之间的所有整数序列，分别求解 **Xor 优化问题**。 - 当 $A=(0,0)$ 时，答案为 $0$ - 当 $A=(0,1)$ 时，答案为 $1$ - 当 $A=(1,0)$ 时，答案为 $1$ - 当 $A=(1,1)$ 时，答案为 $1$ 因此，$0+1+1+1=3$，即为答案。 由 ChatGPT 4.1 翻译