题目描述

D 博士最近设计了一款新的密码锁，密码锁的工作原理如下：

密码 $A$ 是一个 $n$ 个数的序列，每个元素都是 $1\sim n$ 之间的一个整数，刚刚安装时，密码锁内部会随机出一个 $1\sim n$ 的排列 $B$，然后根据 $A,B$ 产生一组对比密码 $C$：

其中 $B^{-1}(x)$ 表示元素 $x$ 在排列 $B$ 中的位置。例如，若 $B=\{3,1,2\}$，则 $B^{-1}(3)=1$，$B^{-1}(1)=2$。

这种密码锁有非常优异的性能，比如说就算有人通过黑客手段得到 $C$，他们也不可能轻易地得到正确的 $A$ 输入，而如果没有 $A$，仅仅得到了 $C$ 也是没有用的。出于此，Y 老板向 D 博士订购了一套这样的密码锁，这时一种 D 博士没有考虑到的特殊情况发生了：

Y 老板是一个非常健忘的人，有一天他竟然忘记了自己密码锁的密码！

D 博士立刻取出了对应码 $C$，但是因为不知道 $B$，他仍然无法找出 $A$ 的具体值，于是他把这个艰巨的任务交给你，他的助手。你的任务是，统计所有可能的 $A$ 序列总数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，表示 $C_1,C_2,\dots,C_n$。

输出格式

一个整数表示对于所有可能作为密码的 $A$ 序列的个数。

样例输入 #1

5
1 2 3 4 5

样例输出 #1

1

样例输入 #2

5
2 2 2 2 2

样例输出 #2

5

样例输入 #3

5
3 2 5 2 2

样例输出 #3

120

数据规模与约定

本题共有 $10$ 组输入数据，以下给出各组输入数据的 $n$ 值：