You are given a positive integer $ n $. By $ A $ we mean the set $\{1, 2, 3, \ldots, n\}$. Function $ f : A → A $ is called a permutation if it is injective (for distinct arguments returns distinct values). Function $ f : A → A $ is called idempotent if for every $ i ∈ A $ holds $ f(f(i)) = f(i) $.

You are given a function $ f : A → A $. How many pairs of functions $(g, h)$ satisfy following conditions:

• $ g : A → A $ is a permutation,
• $ h : A → A $ is idempotent,
• for every $ i ∈ A $ holds $ f(i) = h(g(i)) $?

Write a program which:

• reads number $ n $ and description of function $ f $ from the standard input ,
• determines the number of pairs of functions $(g, h)$ satisfying the requirement described above,
• writes the result to the standard output.

Input Format

In the first line of input there is one integer $ n $ ($1 ≤ n ≤ 200\,000$). Second line contains a description of function $ f : f(i)$ ($1 ≤ f(i) ≤ n$) for $ i = 1, \ldots, n $, separated with single spaces.

Output Format

In the first line of output there should be a single integer: the remainder of the division by $1\,000\,000\,007$ of the number of different pairs of functions $(g, h)$ satisfying the requirement.

Example

Input

8
7 4 5 1 7 4 4 1

Output

288