AT_fps_24_s ゲーム

次の問題を **部分問題** と呼びます。 > 頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木および整数 $ K $ が与えられます。ここで $ K=1 $ または $ K=N $ が成り立ちます。 > Alice と Bob がゲームをします。ゲームは以下の手順で進行します。 > > - まず、Alice が頂点 $ 1 $ , 頂点 $ 2 $ , $ \dots $ , 頂点 $ K $ のいずれかに駒を $ 1 $ 個置く。 > - その後、Bob から初めて交互に次の操作を繰り返す：駒が置かれている頂点に隣接する頂点のうちまだ駒が置かれたことがない頂点を $ 1 $ 個選び、その頂点に駒を動かす。 > - 自分の手番で操作ができなくなった人が負けで、そうでない人が勝ちとなる。 > > 双方が最適にゲームをした時、勝つのはどちらですか？ 整数 $ U $ および $ \mathrm{type} \in \lbrace 1, 2 \rbrace $ が与えられます。 $ N = 2, 3, \dots, U $ について次の問題を解いてください。 - 整数 $ N, K $ が与えられる。ここで $ K $ の値は $ \mathrm{type}=1 $ のとき $ 1 $ を、 $ \mathrm{type}=2 $ のとき $ N $ を取る。 この $ N, K $ が部分問題の $ N, K $ と一致するとする。この時、部分問題の入力としてあり得る、頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木は $ N^{N-2} $ 個あるが、このうち部分問題の答えが Alice であるような木の個数を $ 998244353 $ で割った余りを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ U $ $ \mathrm{type} $

$ U-1 $ 行出力せよ。 $ i $ 行目には $ N=i+1 $ の時の答えを出力せよ。

### 配点 この問題は次のように採点される。 - $ \mathrm{type}=1 $ を満たすデータセットに正解した場合、 $ 3 $ 点が与えられる。 - $ \mathrm{type}=2 $ を満たすデータセットに正解した場合、 $ 3 $ 点が与えられる。 ### Sample Explanation 1 $ \mathrm{type}=1 $ の時、常に $ K=1 $ が成り立ちます。 $ N=3 $ の場合、条件を満たす木は $ 1-2-3 $ と辺が結ばれた木と $ 1-3-2 $ と辺が結ばれた木の $ 2 $ 個です。 ### Sample Explanation 2 $ \mathrm{type}=2 $ の時、常に $ K=N $ が成り立ちます。 ### Constraints - $ 2 \leq U \leq 2.5 \times 10^5 $ - $ \mathrm{type} \in \lbrace 1, 2 \rbrace $ - 入力される値は全て整数