#arc086c. [arc086_c]Smuggling Marbles

[arc086_c]Smuggling Marbles

题目大意:

Sunke有一棵N + 1个点的树,其中0为根,每个点上有0或1个石子,Sunke会不停的进行如下操作直至整棵树没有石子:

把0上面的石子从树上拿走放入口袋;

把每个点上的石子移到其父亲上;

对于每个点,若其石子数≥ 2,则移除该点所有石子(不 放入口袋)。

求对于所有2N+12^{N+1}种放置石子的方案,最终Sunke口袋中石子数的和为多少,对1000000007取模。

1 ≤ N < 200000,有一部分数据满足1 ≤ N < 2000。

fromDOFY