配点 : $600$ 点

問題文

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

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

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

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

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

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq B \leq 10^7$
• $N \leq 2^B$
• $N, B$ は整数

入力

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

$N$ $B$

出力

答えを出力せよ。

2 2

5

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

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

2022 1119

293184537

200000 10000000

383948354