Ex - make 1 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

次の条件を満たす非負整数列 S を 良い数列 と呼びます。

  • S の(連続とは限らない)非空な部分列 T であって、T のすべての要素のビットごとの xor が 1 であるようなものが存在する。

空の数列 A 、および 0 以上 2^B 未満の整数が 1 つずつ書かれた 2^B 枚のカードがあります。
あなたは次の操作を A が良い数列になるまで繰り返します。

  • カードを 1 枚自由に選び、カードに書かれている数を A の末尾に追加する。そして選んだカードを食べる。(食べたカードはその後選ぶことはできない)

操作後の A としてあり得る数列のうち長さが N であるものは何種類ありますか？ 答えを \text{mod }998244353 で出力してください。

ビットごとの xor とは？ 非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 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

操作後の A としてあり得る数列のうち長さが 2 であるものは次の 5 種類です。

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

入力例 2

2022 1119

出力例 2

293184537

入力例 3

200000 10000000

出力例 3

383948354

Score : 600 points

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