순열과 순열

길이 $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 5 \\, 000$)

두 번째 줄에 순열 $A$의 원소 $A\_1, \\, A\_2, \\, \cdots, \\, A\_N$이 공백으로 구분되어 주어진다. ($1 \leq A\_i \leq N$, $i \neq j$이면 $A\_i \neq A\_j$)

조건을 만족하는 일대일 대응 $f$의 개수를 $998 \\, 244 \\, 353$으로 나눈 나머지를 출력하라.

길이가 $N$인 순열이란 순열의 원소로 $1$부터 $N$까지의 정수가 모두 빠짐없이 단 한 번씩 나오는 수열을 의미한다. 즉, 순열 $A = \left(A\_1, \\, A\_2 , \\, \cdots, \\, A\_N\right)$는 아래 조건을 만족한다.

• $A\_i$는 $1$ 이상 $N$ 이하의 정수
• $i \neq j$이면 $A\_i \neq A\_j$

정의역이 $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$을 의미한다.

함수 $f: D \rightarrow C$가 일대일 함수(단사 함수)가 되기 위해서는, 임의의 $x\_1, \\, x\_2 \in D$에 대하여

$f(x\_1) = f(x\_2) \implies x\_1 = x\_2$

가 성립해야한다. 즉, 서로 다른 원소는 항상 서로 다른 함수값에 대응되는 함수를 의미한다.

함수 $f: D \rightarrow C$가 일대일 대응(전단사 함수)가 되기 위해서는, 함수 $f$가 일대일 함수이며 공역과 치역이 같아야 한다. 즉,

$\forall y \in C, \exists! x \in D \\, \text{s.t.} f(x) = y$

이면 $f$를 일대일 대응이라고 한다.