背景

hzhwcmhf和妹子站在江边,晶莹的雪花随着清风扑面而来。
“我,相当喜欢雪花呢。”
“……”
“你,一个人没问题吗?”
“要走了么?”
“……嗯,大概是的。”
“不能留下来么?”
“不行啦。……这样吧”妹子随手接住了一片雪花,“如果有一天,你能找到这条江中的所有这样子的雪花,我大概就能回到你身边吧……”
一阵疾风吹过,夹杂着大片雪花,hzhwcmhf不禁闭上了眼睛。
再次睁开时,眼前只留下了手中的一片雪花……

描述

一片雪花可以由一个有n个结点,n-1条边的连通图来描述。
妹子留下来的任务就是让hzhwcmhf找到所有与目标结构相同的雪花。
但是这条寒江中的雪花有些特别的地方,每片雪花都有K(0\leq k\leq n)个极寒点。如果两个极寒点由一条边相连,那么这片雪花会因为不稳定而分解。
对于两个图A、B,有以下两种关系:
1)存在一种方式使得将A的顶点重新标号后,对于任意一条边(u,v)要么在A、B中同时出现,要么在A、B中都不出现。
2)在满足条件1的情况下,以同样的标号方式,满足结点v要么在A、B中都为极寒点,要么在A、B中都不是极寒点。
对于满足条件1的图A、B,我们称它们是结构相同的。
对于满足条件2的图A、B,我们称它们是完全相同的。
现在摆在hzhwcmhf面前的一大问题是,与目标结构相同的雪花中,到底有多少个不完全相同的呢?
也就是说,求一棵无根树上本质不同的独立集的个数。(请参照上文理解)
妹子的离去让hzhwcmhf悲痛欲绝,但是他没有放弃,因此他需要你的帮助。

输入格式

第一行有一个正整数n,代表目标雪花的结点数,结点以1, 2, \cdots, n编号。
接下来有n-1行,每行两个正整数u、v,代表u、v两个结点间有一条边。保证1 \leq v, u \leq n
输入保证图为一个连通图。

输出格式

输出一行一个非负整数,即与目标雪花结构相同中,不完全相同的雪花个数。
由于答案可能较大,请输出答案mod 1000000007的值。

样例输入

更多样例和福利数据请见pdf
样例输入1
1
样例输入2
5
1 2
1 3
1 4
1 5

样例输出

样例输出1:
2
样例输出2:
6

样例解释

样例解释1
只有一个点,两种可能:该点不为极寒点或者该点为极寒点。
样例解释2
注意到图能够旋转,那么有以下方式。注意极寒点不能相邻,且2,3,4,5完全等价。

(hzhwcmhf:谁注意到这好像甲烷的取代物的同分异构啊……)
(VFleaKing:orz!!!!)

数据范围与约定

对于10%的数据,n\leq 1000。保证在与目标结构相同的所有图中,不存在一种方式重新标号后与原来完全相同。
对于另外20%的数据,n\leq 1000。保证输入的图为一条链。
对于另外30%的数据,n\leq 1000。保证输入的图中存在一个点,如果将该点当成根,那么该点的所有子树结构相同(即有根树同构)。
对于100%的数据,n\leq 500000

来源

hzhwcmhf

Hint

hzhwcmhf:我没妹子,以上都是我乱想的。

吐槽

VFleaKing: 本来要延续江雪的孤独情怀的,结果hzhwcmhf非要晒妹,怎么都劝不住!简直就是丧心病狂!
hzhwcmhf:我黑了自己娱乐了大众,这不是一种为人民扫广场的奉献精神么。