Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

E. Casinos and travel

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJohn 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 10^{9} + 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 10^{9} + 7.

Examples

Input

2

1 2

Output

4

Input

3

1 2

2 3

Output

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 03:45:29 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|