#P18471. Random Tree Parking
Random Tree Parking
Random Tree Parking
停车函数是一种组合对象,最初由 Konheim 和 Weiss 在研究哈希表的线性探测冲突处理方法时引入。作为狂热的数学爱好者,Bobo 想研究树上的停车函数。
考虑一个形状为树 的停车场。树有 个顶点,编号为 ,以顶点 为根,每条边都指向根的方向。共有 名司机,第 名司机有一个偏好的停车位 。
司机按照 的顺序依次到达。每名司机先尝试停在自己偏好的顶点:如果该顶点为空,就停在那里;否则沿着指向根的边行驶,停在途中遇到的第一个空顶点。如果沿这条路径找不到空顶点,就离开停车场,停车失败。
如果序列 能让所有司机都成功停车,就称它为树 的一个停车函数。
例如,下图的树只有两个顶点。序列 不是停车函数,序列 、、 是它的三个停车函数。


现在给定一棵有 个顶点的树 ,求它的停车函数数量。Bobo 也热衷于随机性,因此树按以下方式随机生成:对于每个 ,独立地从 中等概率选择顶点 ,并让顶点 指向 。
答案可能很大,请输出它对质数 取模的结果。这里求的是输入这棵树的停车函数数量。
输入格式
第一行一个整数 (),表示树的顶点数。
第二行有 个整数 (),其中 表示顶点 指向的唯一顶点。可以假设各个 都是独立地从 中等概率选出的。
原题保证本题测试集数量不超过 。每个输入文件是一棵树,没有多组数据的组数 。
输出格式
输出一个整数,表示输入树的停车函数数量对 取模的结果。
样例 1
输入:
3
1 1
输出:
12
样例 2
输入:
3
1 2
输出:
16
样例 3
输入:
4
1 2 3
输出:
125
样例 4
输入:
8
1 2 3 1 3 4 3
输出:
1198736
样例 5
输入:
15
1 2 2 2 2 3 3 2 7 7 3 10 3 13
输出:
938578089