멱등 함수

양의 정수 $n$이 주어진다. 집합 $A = \{1, 2, 3, \ldots, n\}$이라고 하자. 함수 $f : A \to A$가 서로 다른 입력을 항상 서로 다른 값으로 보내면(즉 단사이면) 이 함수를 순열이라고 부른다. 함수 $f : A \to A$가 모든 $i \in A$에 대해 $f(f(i)) = f(i)$를 만족하면 이 함수를 멱등 함수라고 부른다.

함수 $f : A \to A$가 주어진다. 다음 조건을 모두 만족하는 함수 쌍 $(g, h)$의 개수를 구하여라.

• $g : A \to A$는 순열이다.
• $h : A \to A$는 멱등 함수이다.
• 모든 $i \in A$에 대해 $f(i) = h(g(i))$이다.

개수가 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $n$ ($1 \le n \le 200\,000$)이 주어진다.

둘째 줄에 함수 $f$의 정의가 주어진다. $f(1), f(2), \ldots, f(n)$ ($1 \le f(i) \le n$)이 공백 하나로 구분되어 주어진다.

조건을 만족하는 서로 다른 함수 쌍 $(g, h)$의 개수를 $10^9 + 7$로 나눈 나머지를 첫째 줄에 출력한다.