For a permutation $$$p$$$ with length $$$n$$$, consider a graph consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ , with a directed edge $$$u \to v$$$ iff $$$p_u=v$$$. Since every vertex has exactly one incoming edge and one outgoing edge, the graph must be made up of several cycles.

Then the problem can be rephrased as follows:

There are $$$n$$$ chesses on the graph. Initially, chess $$$i(1 \le i \le n)$$$ is on the vertex $$$p_i$$$. Every turn, all chesses will simultaneously move forward along one edge. After how many turns, every chess $$$i$$$ is exactly on vertex $$$i$$$ (for the first time)?

The answer to the problem is obviously the $$$\operatorname{lcm}$$$ of the lengths of the cycles in the graph minus one. ($$$\operatorname{lcm}$$$: the Lowest Common Multiple)

By calculating $$$\gcd$$$ (Greatest Common Divisor) in $$$O(\log{n})$$$ time, we can eaily get an $$$O(n\log{n})$$$ solution. However, the answer to the problem may be too large, so that probably we need to get the answer modulo by some number.

Instead of calculate $$$\operatorname{lcm}$$$ directly, we can precompute the prime factors of the lengths of the cycles, so that we can simply calculate $$$\max$$$ of the exponents of each prime factor. Finally, we just need to multiple the powers of the primes together, getting the answer modulo by some number. The total time complexity is $$$O(n)$$$, implementing properly.