{"raw_statement":[{"iden":"problem statement","content":"We define the following as a **subproblem**:\n\n> You are given a tree with $N$ vertices labeled $1$ through $N$, and an integer $K$ where $K=1$ or $K=N$.  \n> Alice and Bob play a game with the following rules:\n> \n> *   First, Alice places a piece on one of the vertices $1, 2, \\dots, K$.\n> *   Then, starting with Bob, they alternately perform the following operation:\n>     *   Choose a vertex adjacent to the current piece that has not yet been visited, and move the piece there.\n> *   The player who cannot make a move on their turn loses, and the other player wins.\n> \n> Assuming both play optimally, determine who wins the game.\n\nYou are given an integer $U$ and a value $\\mathrm{type} \\in {1, 2}$.  \nFor each $N = 2, 3, \\dots, U$, solve the following problem:\n\n*   You are given integers $N$ and $K$, where  \n    $K = 1$ if $\\mathrm{type} = 1$, and $K = N$ if $\\mathrm{type} = 2$.  \n    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$.  \n    Among them, count how many trees yield the answer \"Alice\" for the subproblem, and output the result modulo $998244353$."},{"iden":"constraints","content":"*   $2 \\leq U \\leq 2.5 \\times 10^5$\n*   $\\mathrm{type} \\in {1, 2}$\n*   All input values are integers"},{"iden":"scoring","content":"This problem has the following scoring rules:\n\n*   If you solve all datasets with $\\mathrm{type} = 1$, you will earn $3$ points.\n*   If you solve all datasets with $\\mathrm{type} = 2$, you will earn $3$ points."},{"iden":"input","content":"The input is given from standard input in the following format:\n\n$U$ $\\mathrm{type}$"},{"iden":"sample input 1","content":"4 1"},{"iden":"sample output 1","content":"0\n2\n3\n\nWhen $\\mathrm{type} = 1$, $K = 1$ always holds.  \nFor $N = 3$, there are $2$ valid trees: one with edges $1-2-3$, and another with edges $1-3-2$."},{"iden":"sample input 2","content":"10 2"},{"iden":"sample output 2","content":"0\n3\n4\n125\n576\n16807\n154624\n4782969\n69760000\n\nWhen $\\mathrm{type} = 2$, $K = N$ always holds."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}