시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB197736.842%

## 문제

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.

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 ≤ 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 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.

## 예제 입력 1

5
3 5 1 2 4


## 예제 출력 1

3


## 예제 입력 2

8
7 5 1 6 8 2 3 4


## 예제 출력 2

4


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]