atcoder#ABC278H. [ABC278Ex] make 1

[ABC278Ex] make 1

配点 : 600600

問題文

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

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

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

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

操作後の AA としてあり得る数列のうち長さが NN であるものは何種類ありますか? 答えを mod 998244353\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)。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1B1071 \leq B \leq 10^7
  • N2BN \leq 2^B
  • N,BN, B は整数

入力

入力は以下の形式で標準入力から与えられる。

NN BB

出力

答えを出力せよ。

2 2
5

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

  • (0,1)(0, 1)
  • (2,1)(2, 1)
  • (2,3)(2, 3)
  • (3,1)(3, 1)
  • (3,2)(3, 2)
2022 1119
293184537
200000 10000000
383948354