分数: 600 点
问题陈述
一个序列 非负整数的 S 被称为 好的序列 如果:
- 存在一个非空(不一定是连续的)子序列 T of S 使得所有元素的按位异或 T is 1.
有一个空序列 A,和 2^B 卡片之间的每个整数
上面写着 0 和 2^B-1 。
重复以下操作,直到 A 成为一个好的序列:
- 你自由选择一张卡片,并将上面写的整数附加到卡片的尾部 A。 然后,你吃掉这张卡。 (一旦吃完,就不能再选择该卡。)
长度为多少个序列 N 可以是最终的 A 操作之后? 求计数模数 998244353.
什么是按位异或?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B定义如下。- 当 A \oplus B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq B \leq 10^7
- N \leq 2^B
- N 和 B 是整数。
输入
输入由标准输入按以下格式给出:
N B
输出
打印答案。
示例输入 1
2 2
示例输出 1
5
以下五个序列的长度 2 可以是最终的 A 操作后。
- (0, 1)
- (2, 1)
- (2, 3)
- (3, 1)
- (3, 2)
示例输入 2
2022 1119
示例输出 2
293184537
示例输入 3
200000 10000000
示例输出 3
383948354