시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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

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]

예제 입력 2

8
7 5 1 6 8 2 3 4

예제 출력 2

4