#P18100. Astana Hard Metro
Astana Hard Metro
Astana Hard Metro
阿斯塔纳的地铁以如下方式建设:第一年建立编号为 的中心站。此后第 年建立编号为 的新站,并选择一个满足 的已有车站,修建一条从新站通向它的轨道。列车只能沿轨道向中心站行驶。
地铁因此形成一棵以 为根的树。没有其他车站能沿一条轨道到达的车站称为终点站,也就是树的叶子。
一个车站的换乘复杂度等于能沿一条轨道直接到达它的车站数量,即它的儿子数;终点站的换乘复杂度定义为 。
目前已经建立了 个车站。从下一年开始,每年仍然新建一个车站,但新车站连接的父亲将从当时所有已有车站中等概率随机选择。
Pupa 将在 年后参观地铁,届时共有 个车站。她会从届时所有终点站中等概率随机选择一个,乘车到达中心站,并在导览图上划去这条路径上的所有车站,包括出发的终点站和中心站。
她把没有划去的车站的换乘复杂度相乘,得到参观的结果。复杂度取自参观前完整地铁的导览图;划去车站不会重新计算其他车站的复杂度。如果所有车站都被划去,则结果为 。
求结果的期望值,对 取模。期望若表示为分数 ,输出 。
输入格式
第一行包含两个整数 (,)。
第二行包含 个整数 ,其中 ,表示目前已有车站的父亲。
输出格式
输出一个整数,表示所求期望对 取模的结果。
样例 1
输入:
4 1
1 1 1
输出:
1
样例 2
输入:
12 2
1 1 2 2 3 3 4 5 6 4 5
输出:
413192725
样例 3
输入:
2 77
1
输出:
253554867