34155번 - 수열과 수열 2 서브태스크

문제

길이 $N$의 수열 $A = \left(A_1, ,円 A_2 , ,円 \cdots, ,円 A_N\right)$이 주어진다. 이때, 다음을 만족하는 함수 $f$의 개수를 구하라.

• $f : \left\{1, ,円 2, ,円 \cdots, ,円 N \right\} \rightarrow \left\{1, ,円 2, ,円 \cdots, ,円 N \right\}$. 즉, $f$는 정의역과 공역으로 집합 $\left\{1, ,円 2, ,円 \cdots, ,円 N \right\}$을 가진다.
• 1ドル \leq i \leq N$을 만족하는 모든 정수 $i$에 대해, $f(i) \neq i$이고 $f(i) \neq A_i$이다.

이때, 답이 매우 커질 수 있으므로 998ドル ,円 244 ,円 353$으로 나눈 나머지를 출력하라. 998ドル ,円 244 ,円 353$은 소수이다.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다. $(2 \leq N \leq 200 ,円 000)$

두 번째 줄에 수열 $A$의 원소 $A_1, ,円 A_2, ,円 \cdots, ,円 A_N$이 공백으로 구분되어 주어진다. (1ドル \leq A_i \leq N$)

출력

조건을 만족하는 함수 $f$의 개수를 998ドル ,円 244 ,円 353$으로 나눈 나머지를 구하라.

제한

서브태스크

노트

정의역이 $D,ドル 공역이 $C$인 함수 $f : D \rightarrow C$는 집합 $D$의 각 원소에 대해 집합 $C$의 원소를 하나씩 대응시키는 규칙이다. 이때 모든 대응값은 $C$에 속하며, 함수는 $D$의 모든 원소에 대해 정의되어야 한다. 즉, 모든 $x \in D$에 대해 유일한 $f(x) \in C$가 존재하는 대응 규칙을 의미한다.

함수 $f: D \rightarrow C$의 치역은 정의역 $D$의 원소들이 $f$에 의해 실제로 대응되는 공역 $C$의 원소들의 집합이다. 즉, $f$의 치역은 $\{ f(x) \mid x \in D \} \subseteq C$을 의미한다.