AT_fps_24_s ゲーム

We define the following as a **subproblem**: > You are given a tree with $ N $ vertices labeled $ 1 $ through $ N $ , and an integer $ K $ where $ K=1 $ or $ K=N $ . > Alice and Bob play a game with the following rules: > > - First, Alice places a piece on one of the vertices $ 1, 2, \dots, K $ . > - Then, starting with Bob, they alternately perform the following operation: > - Choose a vertex adjacent to the current piece that has not yet been visited, and move the piece there. > - The player who cannot make a move on their turn loses, and the other player wins. > > Assuming both play optimally, determine who wins the game. You are given an integer $ U $ and a value $ \mathrm{type} \in {1, 2} $ . For each $ N = 2, 3, \dots, U $ , solve the following problem: - You are given integers $ N $ and $ K $ , where $ K = 1 $ if $ \mathrm{type} = 1 $ , and $ K = N $ if $ \mathrm{type} = 2 $ . Suppose these values match the $ N $ and $ K $ of the subproblem above. There are $ N^{N-2} $ possible trees with $ N $ vertices labeled $ 1 $ through $ N $ . Among them, count how many trees yield the answer "Alice" for the subproblem, and output the result modulo $ 998244353 $ .

The input is given from standard input in the following format: > $ U $ $ \mathrm{type} $

Print $ U - 1 $ lines. On the $ i $ -th line, output the answer for $ N = i + 1 $ .

### Scoring This problem has the following scoring rules: - If you solve all datasets with $ \mathrm{type} = 1 $ , you will earn $ 3 $ points. - If you solve all datasets with $ \mathrm{type} = 2 $ , you will earn $ 3 $ points. ### Sample Explanation 1 When $ \mathrm{type} = 1 $ , $ K = 1 $ always holds. For $ N = 3 $ , there are $ 2 $ valid trees: one with edges $ 1-2-3 $ , and another with edges $ 1-3-2 $ . ### Sample Explanation 2 When $ \mathrm{type} = 2 $ , $ K = N $ always holds. ### Constraints - $ 2 \leq U \leq 2.5 \times 10^5 $ - $ \mathrm{type} \in {1, 2} $ - All input values are integers