問題文

想定解に誤りが見つかったため、正しい解法に差し替えたうえで問題の制約を変更しました。(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 個存在するようなものの総数

制約

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

入力例 1

3 2

出力例 1

2
4
2

• 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 つです。

入力例 2

7 9

出力例 2

1236360
1801104
1168800
444960
111630
17796
2319

入力例 3

10 1000000000

出力例 3

463421383
80897715
609130572
681545366
345958046
718253740
76864047
286280738
642996694
527041309