题目描述

给定一个由 $1$ 到 $N$ 组成的排列 $A$，即：

• $1 \le A[i] \le N$；
• 对任意 $i \ne j$，都有 $A[i] \ne A[j]$。

请你求出满足下列条件的排列 $B$ 的个数：

也就是说，对于每一个 $x$，都要满足上式。

请编写程序 perm 计算这样的排列 $B$ 有多少个。由于答案可能很大，只需输出它对 $1\,000\,000\,007$ 取模后的结果。

输入格式

第一行输入一个正整数 $N$，表示排列 $A$ 的长度。

第二行输入 $N$ 个整数：$A[1], A[2], \dots, A[N]$。

输出格式

输出一个整数，表示满足条件的排列 $B$ 的个数，对 $1\,000\,000\,007$ 取模。

数据范围

• $1 \le N \le 1000000$
• 对所有 $1 \le i \le N$，都有 $1 \le A[i] \le N$
• $A$ 中所有数互不相同

子任务与评分

• 子任务 1（10 分）：$1 \le N \le 9$
• 子任务 2（34 分）：$1 \le N \le 100$，并且满足条件的排列 $B$ 的数量小于 $1000000$
• 子任务 3（56 分）：无额外限制

子任务 1 和子任务 2 只有在该子任务全部测试通过时才获得对应分数。子任务 3 的每个测试单独计分。

样例

输入

5
3 1 2 5 4

输出

6

样例说明

这里：

• $A[1] = 3$
• $A[2] = 1$
• $A[3] = 2$
• $A[4] = 5$
• $A[5] = 4$

原题中给出了其中两个可行的排列 $B$：

1. $B[1] = 1, B[2] = 2, B[3] = 3, B[4] = 5, B[5] = 4$

   检查：

   • $A[B[1]] = B[A[1]] = 3$
   • $A[B[2]] = B[A[2]] = 1$
   • $A[B[3]] = B[A[3]] = 2$
   • $A[B[4]] = B[A[4]] = 4$
   • $A[B[5]] = B[A[5]] = 5$

2. $B[1] = 2, B[2] = 3, B[3] = 1, B[4] = 4, B[5] = 5$

   检查：

   • $A[B[1]] = B[A[1]] = 1$
   • $A[B[2]] = B[A[2]] = 2$
   • $A[B[3]] = B[A[3]] = 3$
   • $A[B[4]] = B[A[4]] = 4$
   • $A[B[5]] = B[A[5]] = 5$