AT_kupc2024_i I Hate Xor Sum

正整数 $ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N\ M $

$ M $ 行にわたって出力せよ。 $ i\ (1\leq i\leq M) $ 行目には $ S=i $ のときの答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - $ N \leq 3000, M = 1 $ を満たすデータセットに正解した場合 $ 1 $ 点が与えられる。 - $ N \leq 10^6, M = 1 $ を満たすデータセットに正解した場合追加で $ 1 $ 点が与えられる。 ### Sample Explanation 1 例えば $ 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 $ ### Sample Explanation 2 $ 998244353 $ で割ったあまりを出力してください。 ### Constraints - $ 1\leq N\leq 10^{9} $ - $ 1\leq M\leq 10^{5} $ - 入力は全て整数