{"problem":{"name":"Game","description":{"content":"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 followin","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"fps_24_s"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $2 \\leq U \\leq 2.5 \\times 10^5$\n*   $\\mathrm{type} \\in {1, 2}$\n*   All input values are integers\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$U$ $\\mathrm{type}$\n\n## Scoring\n\nThis 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.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_s","tags":[],"sample_group":[["4 1","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$."],["10 2","0\n3\n4\n125\n576\n16807\n154624\n4782969\n69760000\n\nWhen $\\mathrm{type} = 2$, $K = N$ always holds."]],"created_at":"2026-03-03 11:01:14"}}