AT_pakencamp_2022_day3_h Exactly K Square Numbers

**想定解に誤りが見つかったため、正しい解法に差し替えたうえで問題の制約を変更しました。( $ M \le 10^{12} $ から $ M \le 10^9 $ )影響を受けた方、申し訳ありません。(15:29)** 正整数 $ N,M $ が与えられます。 $ 0\leq K\leq N-1 $ を満たす全ての $ K $ に対して、次の値を $ 998244353 $ で割った余りを求めてください。 - $ 1 $ 以上 $ M $ 以下の整数のみからなる長さ $ N $ の数列 $ A=(A_1,A_2,\ldots,A_N) $ であって、 $ A_i \times A_{i+1} $ が平方数であるような $ i\,(1\leq i\leq N-1) $ がちょうど $ K $ 個存在するようなものの総数

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

$ N $ 行出力せよ。 $ i\, (1\leq i\leq N) $ 行目には、 $ K=i-1 $ の時の答えを出力せよ。

### Sample Explanation 1 - $ K=0 $ のとき、数えるべき $ A $ は $ (1,2,1),(2,1,2) $ の $ 2 $ つです。 - $ K=1 $ のとき、数えるべき $ A $ は $ (1,1,2),(1,2,2),(2,1,1),(2,2,1) $ の $ 4 $ つです。 - $ K=2 $ のとき、数えるべき $ A $ は $ (1,1,1),(2,2,2) $ の $ 2 $ つです。 ### Constraints - $ 2\leq N\leq 2000 $ - $ 1 \le M \le 10^{9} $ - 入力は全て整数