信息传递
题目描述
给定置换
$$
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$ 。
输出格式
输出答案。
输入输出样例
输入样例 #1
3
2 1 3
输出样例 #1
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$。