题目描述

PCT 提出了如下问题。

异或优化问题

给定一个长度为 $N$ 的非负整数序列：$A_1,A_2,...,A_N$。当可以选择 $A$ 中的任意数量的元素时，所选值的最大可能 $\\mathrm{XOR}$ 是多少？

Nyaan 认为这太简单了，对其进行了修改，改为了以下问题。

许多异或优化问题

由介于 $0$ 和 $2^M-1$ 之间的整数组成的长度为 $N$ 的序列有 $2^{NM}$ 个。求所有这些序列上 异或优化问题 的答案之和，对 $998244353$ 取模。

解决 许多异或优化问题。

什么是按位 $\\mathrm{XOR}$？

非负整数 $A$ 和 $B$ 的按位 $\\mathrm{XOR}$，记作 $A \\oplus B$，定义如下：

• 将 $A \\oplus B$ 以二进制表示，第 $2^k$ 位（$k \\geq 0$）的数字为 $1$ 当且仅当 $A$ 和 $B$ 中只有一个数字为 $1$，否则为 $0$。

例如，我们有 $3 \\oplus 5 = 6$（二进制表示为 $011 \\oplus 101 = 110$）。
通常情况下，$k$ 个非负整数 $p_1, p_2, p_3, \\dots, p_k$ 的按位 $\\mathrm{XOR}$ 定义为 $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$。我们可以证明该值不依赖于 $p_1, p_2, p_3, \\dots, p_k$ 的顺序。

约束条件

• $1 \\le N,M \\le 250000$
• 所有输入的值都是整数。

输入

输入以标准格式给出，格式如下：

$N$ $M$

输出

输出答案。

示例输入1

2 1

示例输出1

3

我们需要解决对所有长度为 $2$，并由介于 $0$ 和 $1$ 之间的整数组成的序列上的 异或优化问题。

• 当 $A=(0,0)$ 时，答案为 $0$。
• 当 $A=(0,1)$ 时，答案为 $1$。
• 当 $A=(1,0)$ 时，答案为 $1$。
• 当 $A=(1,1)$ 时，答案为 $1$。

因此，最终答案为 $0+1+1+1=3$。

示例输入2

3 4

示例输出2

52290

示例输入3

1234 5678

示例输出3

495502261