Counting Permutations with Prescribed n-th Power

Let f be a permutation on the set {1,2,…,n} given in two–line notation by

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

and let its cycle–decomposition be \(\{C\}\). We want to count the number of permutations \(g\) such that

$$ g^n = f, $$

where the power \(g^n = g\circ g\circ \cdots \circ g\) (\(n\) times) is taken by composition. Since the answer can be huge, print it modulo 998244353.

Explanation and approach:

A classical approach is to work cycle–by–cycle. Write the cycle–decomposition of f and for each cycle of length \(L\) (appearing \(m\) times) determine in how many ways the cycles can be "merged" into cycles of the unknown permutation \(g\) so that \(g^n\) reproduces those cycles. It is known that if a cycle in \(g\) has length \(d\) then \(g^n\) produces \(\gcd(d,n)=r\) cycles each of length \(\frac{d}{r}\). Thus in order to produce an image cycle of length \(L\) in \(f\) we must have

$$\frac{d}{\gcd(d,n)}=L.$$

Writing \(d = L\,r\) and noting that \(r = \gcd(L\,r,n)\) if and only if \(r\) divides \(n\) and \(\gcd(L, n/r)=1\), the key observation is that allowed block sizes for cycles of f of length \(L\) are exactly those numbers r satisfying:

$$r\mid n \quad \text{and} \quad \gcd(L, n/r)=1.$$

In the solution one groups the \(m\) cycles of length \(L\) into subsets of size \(r\) (for an allowed \(r\)). A g–cycle of length \(L\,r\) will then give rise to r cycles in \(f</em> by taking the n–th power, and one may prove that there are exactly $$ (L\,r)^{r-1} $$ ways to "lift" a group of \(r\) cycles to a cycle in \(g\). Since the cycles of f are labeled, the group–theoretic count boils down to the combinatorial formula $$\text{Ways}(L,m)= m!\;\sum_{\substack{\{x_r\}_{r\in S}\;:\;\sum_{r\in S}r\,x_r=m}}\;\prod_{r\in S}\frac{1}{x_r!\,(r!)^{x_r}}\;\Bigl[(L\,r)^{r-1}\Bigr]^{x_r}, $$

where \(S=\{r\,:\;r\mid n,\;\gcd(L,n/r)=1\}\). The final answer is the product over all different cycle lengths of the value above.

Input and Output formats:

The input begins with an integer n (the size of the permutation) on one line; the next line contains n space separated integers \(a_1,a_2,...,a_n\) which represent the permutation f (i.e. \(f(i)=a_i\)).

The output is a single integer: the number of permutations \(g\) satisfying \(g^n=f\) modulo 998244353.

inputFormat

The first line contains an integer n (the number of elements).
The second line contains n space–separated integers: \(a_1, a_2, \dots, a_n\), where f(i)=a_i.

You may assume that 1 ≤ n ≤ 200 (or similar constraints) and that \(a_1, \dots, a_n\) is a permutation of {1,2,…,n}.

outputFormat

Output a single integer: the answer modulo 998244353.

sample

1
1

1