题目描述
给定一棵拥有 $n$ 个结点的树,$1$ 号点为这棵树的根。请统计,这棵树拥有多少种不同的独立集。
所谓**独立集**,是一个由树上结点构成的子集,树任意一条边的两个点不能同时在独立集里。空集也是一种独立集。
由于独立集数量可能很大,输出种类数模 $1,000,000,007$ 的余数即可。
输入
第一行:单个整数表示 $n$;
第二行:$n-1$ 个整数表示 $p_2$ 到 $p_n$,$p_i$ 表示 $i$ 号点父亲的编号,保证有 $1\leq p_i \lt i$。
输出
单个整数:表示独立集数量模 $1,000,000,007$ 的余数。
样例输入输出
提示
+ 对于 $30\%$ 的数据, $n\leq 20$;
+ 对于 $60\%$ 的数据, $n\leq 5,000$;
+ 对于 $100\%$ 的数据, $1\leq n\leq 200,000$。
样例1说明:一个点构成的独立集有三个,两个点构成的独立集有一个,空集一个,共五个