codeforces#P852E. Casinos and travel
Casinos and travel
Description
John has just bought a new car and is planning a journey around the country. Country has N cities, some of which are connected by bidirectional roads. There are N - 1 roads and every city is reachable from any other city. Cities are labeled from 1 to N.
John first has to select from which city he will start his journey. After that, he spends one day in a city and then travels to a randomly choosen city which is directly connected to his current one and which he has not yet visited. He does this until he can't continue obeying these rules.
To select the starting city, he calls his friend Jack for advice. Jack is also starting a big casino business and wants to open casinos in some of the cities (max 1 per city, maybe nowhere). Jack knows John well and he knows that if he visits a city with a casino, he will gamble exactly once before continuing his journey.
He also knows that if John enters a casino in a good mood, he will leave it in a bad mood and vice versa. Since he is John's friend, he wants him to be in a good mood at the moment when he finishes his journey. John is in a good mood before starting the journey.
In how many ways can Jack select a starting city for John and cities where he will build casinos such that no matter how John travels, he will be in a good mood at the end? Print answer modulo 109 + 7.
In the first line, a positive integer N (1 ≤ N ≤ 100000), the number of cities.
In the next N - 1 lines, two numbers a, b (1 ≤ a, b ≤ N) separated by a single space meaning that cities a and b are connected by a bidirectional road.
Output one number, the answer to the problem modulo 109 + 7.
Input
In the first line, a positive integer N (1 ≤ N ≤ 100000), the number of cities.
In the next N - 1 lines, two numbers a, b (1 ≤ a, b ≤ N) separated by a single space meaning that cities a and b are connected by a bidirectional road.
Output
Output one number, the answer to the problem modulo 109 + 7.
Samples
2
1 2
4
3
1 2
2 3
10
Note
Example 1: If Jack selects city 1 as John's starting city, he can either build 0 casinos, so John will be happy all the time, or build a casino in both cities, so John would visit a casino in city 1, become unhappy, then go to city 2, visit a casino there and become happy and his journey ends there because he can't go back to city 1. If Jack selects city 2 for start, everything is symmetrical, so the answer is 4.
Example 2: If Jack tells John to start from city 1, he can either build casinos in 0 or 2 cities (total 4 possibilities). If he tells him to start from city 2, then John's journey will either contain cities 2 and 1 or 2 and 3. Therefore, Jack will either have to build no casinos, or build them in all three cities. With other options, he risks John ending his journey unhappy. Starting from 3 is symmetric to starting from 1, so in total we have 4 + 2 + 4 = 10 options.