{"problem":{"name":"Flipping Coins","description":{"content":"There are $N$ coins numbered $1, 2, \\ldots, N$ arranged in a row. Initially, all coins face up. Snuke chooses a permutation $p$ of $(1,\\ldots,N)$ with equal probability, and do $N$ operations. The $i$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc134_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ coins numbered $1, 2, \\ldots, N$ arranged in a row. Initially, all coins face up.\nSnuke chooses a permutation $p$ of $(1,\\ldots,N)$ with equal probability, and do $N$ operations. The $i$\\-th operation does the following.\n\n*   If the coin numbered $i$ faces down, do nothing.\n*   If the coin numbered $i$ faces up, turn that coin over and then turn over the coin numbered $p_i$.\n\nAfter the $N$ operations, Snuke will receive $W^k$ yen (Japanese currency) from his mother, where $k$ is the number of coins facing up.\nFind the expected value of the amount Snuke will get, multiplied by $N!$ (it can be proved that this is an integer), modulo $998244353$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq W < 998244353$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $W$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc134_f","tags":[],"sample_group":[["4 2","90\n\n*   When $p=(1,4,2,3)$, the operations go as follows.\n    *   In the $1$\\-st operation, the coin numbered $1$ faces down, and then the coin numbered $1$ faces up.\n    *   In the $2$\\-nd operation, the coin numbered $2$ faces down, and then the coin numbered $4$ faces down.\n    *   In the $3$\\-rd operation, the coin numbered $3$ faces down, and then the coin numbered $2$ faces up.\n    *   In the $4$\\-th operation, nothing is done.\n*   In the end, two coins face up, so he receives $4$ yen."],["2 100","10001"],["200000 12345","541410753\n\n*   Be sure to find the value modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}