#P2899. 含糊的安全锁

    ID: 2006 传统题 1000ms 512MiB 尝试: 15 已通过: 5 难度: 8 上传者: 标签>CF2500提高+/省选-功能图轨道—稳定子定理入度剥离AHU 算法树形 DP固定旋转代表排列数计算模逆元快速幂

含糊的安全锁

题目描述

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

密码 A 是一个 nn 个数的序列,每个元素都是 11 至 nn 之间的一个整数。刚刚安装时,密码锁内部会随机出一个 11 至 nn 的排列 BB,然后根据 A,BA,B 产生一组比对码 CC:

Ci=BABi−1C_i = B_{A_{B_i}}^{-1}

其中 Bi−1B_i^{-1} 表示元素 ii 在 BB 中的位置,比如说:B={3,1,2}B=\{3,1,2\},那么有:B3−1=1,B1−1=2B_3^{-1} =1,B_1^{-1} =2。

这种密码锁有非常优异的性能,比如说就算有人通过黑客手段得到 CC,他们也不可能轻易的得到正确的 AA 输入,而如果没有 AA,仅仅得到了 CC 也是没有用的。

出于此,Y 老板向 D 博士订购了一套这样的密码锁。这时一种 D 博士没有考虑到的特殊情况发生了:

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

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

输入格式

输入文件第一行包含一个整数 nn,第二行包含 nn 个整数表示对比码 CC。

输出格式

输出文件仅包含一个整数,即所有可能的 AA 序列的总数,鉴于答案可能很大,你只需要输出其模 109+710^9+7 的余数即可。

5
3 2 5 2 2
120

数据规模与约定

对于 30%30\% 的数据,1≤n≤81\leq n\leq 8;

对于 100%100\% 的数据,1≤n≤501\leq n\leq 50。