405866: GYM102136 H Tourist Agency

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Tourist Agencytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

For the benefit of their customers, tourist agency "42 best journeys" has chosen N cities, which are connected by N - 1 direct flights and any two of them are connected by air (direct flights and flights with stop-overs). To promote their service, agency has chosen contextual advertising. To avoid annoying repeating ads, provider is only showing unique tours to their customers. Tour includes visiting K (K ≤ N) cities, which are connected by K - 1 direct flights and any two of them are connected by air. Tours are considered unique if one of them has particular city and the second one doesn't.

Head of agency has developed an advertisement strategy and started thinking of their expenses. Provider of contextual ad is charging one US dollar for each advertisement and one Belarusian rouble for each city included in tour. Accountant team is now required to compute final amount of money to be paid. All possible unique tours (ads) have been shown to the customers during this campaign exactly once.

Input

First line contains one integer number N — number of chosen cities. Next N - 1 lines contain two integer numbers Ui and Vi each — indices of cities which are connected by direct flight.

1 ≤ N ≤ 105
1 ≤ Ui, Vi ≤ N
Output

Single line should have two integer numbers — amount of money in US dollars and Belarusian roubles to be paid by agency. Contextual Ads provider bill agency by amount modulo 109 + 7 as a part of their discounts policy.

ExampleInput
5
4 2
2 5
3 2
5 1
Output
17 42

加入题单

上一题 下一题 算法标签: