{"raw_statement":[{"iden":"problem statement","content":"$N$ coins numbered $0,1,\\ldots,N-1$ are arranged in a row. Initially, all coins are face up. Also, you are given a sequence $A$ of length $N$ consisting of integers between $0$ and $N-1$.\nSnuke will choose a permutation $p=(p_1,p_2,\\ldots,p_N)$ of $(1,\\ldots,N)$ at equal probability and perform $N$ operations. In the $i$\\-th $(1\\leq i \\leq N)$ operation,\n\n*   he flips $(A_{p_i}+1)$ coins: coin $(i-1) \\bmod N$, coin $(i-1+1 ) \\bmod N$, $\\ldots$, and coin $(i -1+ A_{p_i}) \\bmod N$.\n\nAfter the $N$ operations, Snuke receives $k$ yen (the currency in Japan) from his mother, where $k$ is the number of face-up coins.\nFind the expected value, modulo $998244353$, of the money Snuke will receive.\nDefinition of expected value modulo $998244353$In this problem, we can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the sought expected value is represented as an irreducible fraction $\\frac{y}{x}$, it is guaranteed that $x$ is indivisible by $998244353$.\nThen, an integer $z$ between $0$ and $998244352$ such that $xz \\equiv y \\pmod{998244353}$ is uniquely determined. Find such $z$."},{"iden":"constraints","content":"*   $1 \\leq N\\leq 2\\times 10^5$\n*   $0\\leq A_i \\leq N-1$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"2\n0 1"},{"iden":"sample output 1","content":"1\n\n$p$ can be either $(1,2)$ or $(2,1)$.\n\n*   If $(1,2)$ is chosen as $p$:\n\nIn the first operation, coin $0$ is flipped, and in the second operation, coin $1$ and coin $0$ are flipped. One coin, coin $0$, results in being face up, so he receives $1$ yen.\n\n*   If $(2,1)$ is chosen as $p$:\n\nIn the first operation, coin $0$ and coin $1$ are flipped, and in the second operation, coin $1$ is flipped. One coin, coin $1$, results in being face up, so he receives $1$ yen.\nTherefore, the expected value of the money he receives is $1$ yen."},{"iden":"sample input 2","content":"4\n3 1 1 2"},{"iden":"sample output 2","content":"665496237\n\nPrint the expected value modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}