405866: GYM102136 H Tourist Agency

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.

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

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 10⁹ + 7 as a part of their discounts policy.

5
4 2
2 5
3 2
5 1

17 42