题目描述

给定置换

$$f = \begin{pmatrix} 1 & 2 & ... & n \\\ a_1 & a_2 & ... & a_n \end{pmatrix} $$

求有多少个置换 $g$ ，满足

$$g ^ n = f$$

答案对 $998244353$ 取模。

输入格式

第一行一个数 $n$ 。

第二行 $n$ 个数 $a_1, a_2, ..., a_n$ 。

输出格式

输出答案。

3
2 1 3

1

提示

样例解释：

有且仅有 $a_1 = 2, a_2 = 1, a_3 = 3$ 满足

$${\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}} ^ 3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} $$

对于 $20 \%$ 的数据，$n \le 10$。

对于 $60 \%$ 的数据，$n \le 1000$。

对于 $100 \%$ 的数据，$n \le {10} ^ 5$。