题目描述

有 $N$ 枚编号为 $0,1,\\ldots, N-1$ 的硬币排成一行。初始时，所有硬币都是正面朝上。同时，你还有一个长度为 $N$ 的序列 $A$，其中的元素是 $0$ 到 $N-1$ 之间的整数。

Snuke 将以相等的概率选择置换 $p=(p_1,p_2,\\ldots,p_N)$，其中 $p$ 是 $(1,\\ldots,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$ 是唯一确定的。找到这样的 $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$。