問題文

正整数 N,M が与えられます。

非負整数からなる長さ N の数列 A について、次を満たす非負整数 X_{i,j}\ (1\leq j\leq i\leq N) が一意に存在します。

• X_{i,1}=A_i\ (1\leq i\leq N)
• X_{i,j}=X_{i-1,j-1}\oplus X_{i,j-1}\ (2\leq j\leq i\leq N)

ただし \oplus はビットごとの排他的論理和を表します。 このとき \sum_{i=1}^{N}\sum_{j=1}^{i}X_{i,j} の値を A の スコア とします。

S=1,2,\dots,M のそれぞれに対し、非負整数からなる長さ N の数列で総和が S であるもの全てについてのスコアの総和を 998244353 で割ったあまりを求めてください。

制約

• 1\leq N\leq 10^{9}
• 1\leq M\leq 10^{5}
• 入力は全て整数

部分点

この問題には複数の部分点が設定されている。

• N \leq 3000, M = 1 を満たすデータセットに正解した場合 1 点が与えられる。
• N \leq 10^6, M = 1 を満たすデータセットに正解した場合追加で 1 点が与えられる。

入力例 1

4 1

出力例 1

18

例えば A=(0,1,0,0) のとき X_{i,j} は以下のようになりスコアは 5 です。

• X_{1,1}=0
• X_{2,1}=1,X_{2,2}=1
• X_{3,1}=0,X_{3,2}=1,X_{3,3}=0
• X_{4,1}=0,X_{4,2}=0,X_{4,3}=1,X_{4,4}=1

入力例 2

202515 1

出力例 2

631322682

998244353 で割ったあまりを出力してください。

入力例 3

1000000000 20

出力例 3

450736580
222005843
791558300
565944390
287066035
818826101
538663305
222889651
450257059
718428507
230132846
653810630
380943894
21756026
863202268
823515972
834078326
615162787
221193562
85328814