#P17495. PM14725 随机距离探测

PM14725 随机距离探测

题目描述

有一棵包含 NN 个顶点的树,顶点编号为 0,1,…,N−10,1,\ldots,N-1。宝藏等概率地藏在某一个顶点中。

每个顶点上都有一个探测器。使用顶点 vv 上的探测器,可以得到 vv 到宝藏所在顶点的树上距离。这里的距离指最短路径经过的边数。

你会把全部 NN 个探测器按一个等概率随机的排列依次使用。当根据已经得到的所有距离信息能够唯一确定宝藏所在顶点时,你会立即停止。

树由数组 parent 描述。对于 i=1,2,…,N−1i=1,2,\ldots,N-1,顶点 ii 与顶点 parenti−1parent_{i-1} 之间有一条边。

设使用探测器数量的期望为 XX。可以证明 X⋅N⋅N!X\cdot N\cdot N! 一定是整数。请输出

X⋅N⋅N!(mod109+7)X\cdot N\cdot N!\pmod {10^9+7}。

输入格式

第一行一个整数 mm,表示 parent 数组的长度,因此 N=m+1N=m+1。

若 m>0m>0,第二行输入 mm 个整数 parent0,parent1,…,parentm−1parent_0,parent_1,\ldots,parent_{m-1}。

输出格式

输出一个整数,表示 X⋅N⋅N!X\cdot N\cdot N! 对 109+710^9+7 取模后的结果。

数据范围

  • 1≤N≤501\le N\le 50,即 0≤m≤490\le m\le 49;
  • 对所有 0≤i<m0\le i<m,有 0≤parenti≤i0\le parent_i\le i。

样例 1

1
0
4

样例 2

2
0 0
22