405866: GYM102136 H Tourist Agency
Description
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.
InputFirst 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.
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.
ExampleInput5Output
4 2
2 5
3 2
5 1
17 42