P15596 [ICPC 2020 Jakarta R] Permutation Transformation

A permutation of $1 \dots N$ is an array of integers $P[1 \dots N]$ such that each integer from $1$ to $N$ appears exactly once in $P[1 \dots N]$. A **transformation** to $P[1 \dots N]$ is defined as changing $P[1 \dots N]$ into another permutation $P'[1 \dots N]$ where $P'[i] = P[P[i]]$ for all $1 \leq i \leq N$. You are given a permutation $P[1 \dots N]$. Your task in this problem is to count the number of distinct permutations you can get by doing a transformation to the given permutation for zero or more times. For example, let $P[1 \dots N] = [3, 5, 1, 2, 4]$. - By doing a transformation, you will change $P$ into $[1, 4, 3, 5, 2]$. - By doing another transformation, you will change $P$ into $[1, 5, 3, 2, 4]$. - By doing another transformation, you will change $P$ into $[1, 4, 3, 5, 2]$ again. Therefore, there are $3$ distinct permutations you can get by doing a transformation for zero or more times. 1. $[3, 5, 1, 2, 4]$ 2. $[1, 4, 3, 5, 2]$ 3. $[1, 5, 3, 2, 4]$

Input begins with a line containing an integer: $N$ ($1 \leq N \leq 100\,000$) representing the number of elements in the given permutation. The next line contains $N$ integers: $P[i]$ ($1 \leq P[i] \leq N$) representing the permutation. The elements in $P[1 \dots N]$ are guaranteed to be unique.

Output in a line an integer representing the number of distinct permutations you can get by doing a transformation to the given permutation for zero or more times, modulo $998\,244\,353$.

#### Explanation for the sample input/output #1 This is the example from the problem description. #### Explanation for the sample input/output #2 There are $4$ distinct permutations you can get by doing a transformation to the given permutation for zero or more times. 1. $[7, 5, 1, 6, 8, 2, 3, 4]$ 2. $[3, 8, 7, 2, 4, 5, 1, 6]$ 3. $[7, 6, 1, 8, 2, 4, 3, 5]$ 4. $[3, 4, 7, 5, 6, 8, 1, 2]$