Permutation Transformation

Time limit1sMemory limit512 MB

Summary

Given a permutation P, count the number of distinct permutations reachable by repeatedly applying P'[i] = P[P[i]], modulo 998244353.

Level: Medium7 of 10
Topics: Math, Combinatorics, Number theory, Implementation
Solved: No attempts yet

Problem

A permutation of 1 . . . N is an array of integers P[1...N] such that each integer from 1 to N appears exactly once in P[1...N]. A transformation to P[1...N] is defined as changing P[1...N] into another permutation P'[1...N] where P'[i] = P[P[i]] for all 1 ≤ i ≤ N.

You are given a permutation P[1...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...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.

[3, 5, 1, 2, 4]
[1, 4, 3, 5, 2]
[1, 5, 3, 2, 4]

Input

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

Output

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.

Examples2

Example 1
Input
```
5
3 5 1 2 4
```
Expected output
```
3
```
Example 2
Input
```
8
7 5 1 6 8 2 3 4
```
Expected output
```
4
```