题目描述

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

5
3 5 1 2 4

3

8
7 5 1 6 8 2 3 4

4

提示

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]$