Score : $600$ points

问题描述

一个由非负整数组成的序列 $S$ 被称为好序列，如果满足以下条件：

• 存在一个非空（不一定连续）的子序列 $T$，使得 $T$ 中所有元素按位异或的结果为 $1$。

给定一个空序列 $A$ 和 $2^B$ 张卡片，每张卡片上分别写有从 $0$ 到 $2^B-1$ 的一个整数。
你需要重复执行以下操作，直到 $A$ 变成一个好序列：

• 自由选择一张卡片，并将其上所写的整数追加到 $A$ 的末尾。然后吃掉这张卡片。（一旦被吃掉，卡片就不能再被选择了。）

在经过这些操作后，最终长度为 $N$ 的序列 $A$ 有多少种可能？请计算结果对 $998244353$ 取模后的数量。

什么是按位异或（bitwise XOR）？两个非负整数 $A$ 和 $B$ 的按位 $\mathrm{XOR}$ 运算，记作 $A \oplus B$，定义如下：

• 当 $A \oplus B$ 表示为二进制时，第 $k$ 位最低位（$k \geq 0$）为 $1$ 当且仅当 $A$ 和 $B$ 的第 $k$ 位最低位中恰好有一个是 $1$，否则为 $0$。

例如：$3 \oplus 5 = 6$（以二进制表示：$011 \oplus 101 = 110$）。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

A sequence $S$ of non-negative integers is said to be a good sequence if:

• there exists a non-empty (not necessarily contiguous) subsequence $T$ of $S$ such that the bitwise XOR of all elements in $T$ is $1$.

There are an empty sequence $A$, and $2^B$ cards with each of the integers between $0$ and $2^B-1$ written on them.
You repeat the following operation until $A$ becomes a good sequence:

• You freely choose a card and append the integer written on it to the tail of $A$. Then, you eat the card. (Once eaten, the card cannot be chosen anymore.)

How many sequences of length $N$ can be the final $A$ after the operations? Find the count modulo $998244353$.

What is bitwise XOR? The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.

• When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.

For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq B \leq 10^7$
• $N \leq 2^B$
• $N$ and $B$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $B$

Output

Print the answer.

Sample Input 1

2 2

Sample Output 1

5

The following five sequences of length $2$ can be the final $A$ after the operations.

• $(0, 1)$
• $(2, 1)$
• $(2, 3)$
• $(3, 1)$
• $(3, 2)$

Sample Input 2

2022 1119

Sample Output 2

293184537

Sample Input 3

200000 10000000

Sample Output 3

383948354

update @ 2024/3/10 11:43:45