给定一棵有 n 个结点的树,1 号点为这棵树的根。请计算,这棵树有多少连通子图,由于答案可能很大,输出答案模 1,000,000,007 的余数即可。
所谓连通子图,是该树的点构成的集合,这些点之间任意两个点的路径上不存在不属于该集合的点。空集不算连通子图。
第一行:单个整数表示 n;
第二行:n−1 个整数表示 p2 到 pn,pi 表示 i 号点父亲的编号,保证有 1≤pi<i。
单个整数表示答案
3 1 1
6
对于 30% 的数据, n≤20;
对于 60% 的数据, n≤5,000;
对于 100% 的数据, 1≤n≤200,000。
样例说明:
{1}
{2}
{3}
{1 2}
{1 3}
{1 2 3}