P4709 信息传递

给定置换 $$ f = \begin{pmatrix} 1 & 2 & ... & n \\\ a_1 & a_2 & ... & a_n \end{pmatrix} $$ 求有多少个置换 $g$ ，满足 $$ g ^ n = f $$ 答案对 $998244353$ 取模。

无

无

样例解释： 有且仅有 $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$。