异或为 1

题目描述

称非负整数序列 $S$ 为「好序列」,如果满足:

存在 $S$ 的一个非空(不要求连续)子序列 $T$,使得 $T$ 中所有元素的按位异或为 $1$。

有一个空序列 $A$,以及写有 $0$ 到 $2^B-1$ 之间每个整数各一张的 $2^B$ 张卡片。

你重复以下操作,直到 $A$ 成为好序列:

自由选择一张卡片,将卡片上写的整数追加到 $A$ 的末尾。然后吃掉这张卡片。(被吃掉的卡片不能再被选择。)

有多少个长度为 $N$ 的序列可以成为操作结束后的最终 $A$?求其个数对 $998244353$ 取模。

什么是按位异或?

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下。

将 $A \oplus B$ 写成二进制时,第 $k$ 位($k \ge 0$)为 $1$,当且仅当 $A$ 和 $B$ 的第 $k$ 位中恰好有一个为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制:$011 \oplus 101 = 110$)。

输入格式

输入按以下格式从标准输入给出:

$N$ $B$

输出格式

输出答案。

样例

2 2

5

以下 5 个长度为 $2$ 的序列可以成为操作结束后的最终 $A$:

$(0, 1)$

$(2, 1)$

$(2, 3)$

$(3, 1)$

$(3, 2)$

2022 1119

293184537

200000 10000000

383948354

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le B \le 10^7$
• $N \le 2^B$
• $N$、$B$ 均为整数。