约翰刚刚买了一辆新车,并计划环游全国。国家有N个城市,其中一些城市通过双向道路连接。有 N - 1 条道路,每个城市都可以从任何其他城市到达。城市被标记为从 1 到 N。
约翰首先必须选择从哪个城市开始他的旅程。之后,他在一个城市度过一天,然后前往一个随机选择的城市,该城市与他当前的城市直接相连,但他尚未访问过。他这样做,直到他无法继续遵守这些规则为止。
为了选择出发城市,他打电话给他的朋友杰克寻求建议。杰克还开始经营一家大型赌场业务,并希望在一些城市开设赌场(每个城市最多 1 个,也许没有)。杰克很了解约翰,他知道如果他访问一个有赌场的城市,他只会在继续他的旅程之前赌博一次。
他还知道,如果约翰心情好地进入赌场,他就会心情不好地离开赌场,反之亦然。由于他是约翰的朋友,他希望约翰在结束旅程的那一刻有一个好心情。出发前约翰心情很好。
Jack可以通过多少种方式为John选择起始城市以及他要建造赌场的城市,使得无论John如何旅行,他最终都会有一个好心情?打印答案模 109 + 7。
输入
第一行,一个正整数N (1 ≤ N ≤ 100000),城市数量。
在接下来的 N - 1 行中,两个数字 a、b (1 ≤ a, b ≤ N) 由一个空格分隔,这意味着城市 a 和 b 通过双向道路连接。
输出
输出一个数字,即问题答案对 109 + 7 求模。
示例
输入 #1
2 1 2
输出 #1
4
输入 #2
3 1 2 2 3
输出 #2
10
注意
示例 1:如果 Jack 选择城市 1 作为 John 的起始城市,他可以建造 0 个赌场,这样 John 就会一直开心,或者在两个城市都建造一个赌场,这样 John 会去城市 1 的赌场,变得不快乐,然后去城市 2,参观那里的赌场并变得快乐,他的旅程就在那里结束,因为他无法回到城市 1。如果 Jack 选择城市 2 作为起始城市,一切都是对称的,所以答案是4。
示例2:如果Jack告诉John从城市1开始,他可以在0个或2个城市建造赌场(总共4种可能性)。如果他告诉他从城市 2 开始,那么约翰的旅程将包含城市 2 和 1,或者包含城市 2 和 3。因此,杰克要么不必建造赌场,要么在所有三个城市建造赌场。如果有其他选择,约翰可能会不高兴地结束他的旅程。从 3 开始与从 1 开始对称,因此总共有 4 + 2 + 4 = 10 个选项。