给定一个正整数 $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))$。

编写一个程序：

• 从标准输入读取整数 $n$ 和函数 $f$ 的描述，
• 确定满足上述要求的函数对 $(g, h)$ 的数量，
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)。第二行包含函数 $f$ 的描述，即 $f(i)$ ($1 \le f(i) \le n$) 的值，对于 $i = 1, \ldots, n$，以空格分隔。

输出格式

第一行输出一个整数：满足要求的不同函数对 $(g, h)$ 的数量除以 $1\,000\,000\,007$ 的余数。

样例

输入 1

8
7 4 5 1 7 4 4 1

输出 1

288