← 返回题目列表

AtCoder · abc278_h

Ex. 使 1

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 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