当前没有测试数据。

反转硬币2

评分：600 分

问题描述

有 $N$ 枚编号为 $0,1,\ldots,N-1$ 的硬币排成一排。初始时，所有的硬币都是正面朝上的。此外，给定一个长度为 $N$ 的序列 $A$，它由 $0$ 和 $N-1$ 之间的整数组成。

Snuke 会以相等的概率选择一个起始排列 $p=(p_1,p_2,\ldots,p_N)$，并进行 $N$ 次操作。在第 $i$ 次操作 ($1\leq i \leq N$) 中， 他将反转第 $(A_{p_i}+1)$ 枚硬币：即将编号为 $((i-1) \bmod N), (i-1+1 \bmod N), \ldots, (i -1+ A_{p_i} \bmod N)$ 的硬币进行反转。

在进行完 $N$ 次操作后，Snuke 从他的母亲那里得到了 $k$ 日元（日本的货币），其中 $k$ 是正面朝上的硬币的数量。

请计算 Snuke 将得到的钱的期望值，对 $998244353$ 取模后的结果。

预期值取模 $998244353$ 的定义

在本问题中，我们可以证明所求的期望值总是一个有理数。 而且，在本问题的约束条件下，当所求的期望值表示为一个既约分数 $\frac{y}{x}$ 时，保证 $x$ 不被 $998244353$ 整除。

那么，可以唯一确定介于 $0$ 和 $998244352$ 之间的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请找出这样的 $z$。

约束条件

• $1 \leq N\leq 2\times 10^5$
• $0\leq A_i \leq N-1$
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出：

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出答案。

样例输入1

2
0 1

样例输出1

1

考虑$p$为$(1,2)$或$(2,1)$的情况：

• 若以$(1,2)$作为$p$：
  • 第一次操作中，硬币$0$被反转；第二次操作中，硬币$1$和硬币$0$都被反转。其中一个硬币，硬币$0$，会变正面朝上，所以他得到了$1$日元。
• 若以$(2,1)$作为$p$：
  • 第一次操作中，硬币$0$和硬币$1$都被反转；第二次操作中，硬币$1$被反转。其中一个硬币，硬币$1$，会变正面朝上，所以他得到了$1$日元。

综上，他得到的钱的期望值为$1$日元。

样例输入2

4
3 1 1 2

样例输出2

665496237

请输出以模 $998244353$ 的形式计算出来的期望值。