Туристическое агентство "42 лучших путешествия" выбрало для себя N городов, которые связаны между собой N - 1 прямыми авиарейсами так, что между двумя любыми городами существует авиамаршрут (возможно, непрямой). Для продвижения своих услуг агенство выбрало контекстную рекламу. Чтобы объявления были не слишком назойливыми, было решено показывать только уникальные туры. Под туром понимается посещение K (K ≤ N) городов, которые связаны K - 1 прямыми авиарейсами и между любыми двумя городами существует авиамаршрут. Туры считаются различными, если в одном из них существует такой город, которого нет в другом.
Придумав такую рекламную стратегию, директор агенства задумался о том, какие расходы понесет компания. За каждое объявление поставщик контекстной рекламы выставляет счет в один доллар США, а за каждый город, входящий в тур – один белорусский рубль. Теперь бухгалтерии необходимо выяснить, сколько агентство заплатит поставщику услуг, если известно, что все возможные уникальные туры были показаны пользователям ровно один раз.
В первой строке задается целое число N — количество городов для путешествий. В следующих N - 1 строках задается по два целых числа Ui и Vi — номера городов, между которыми существует прямой авиарейс.
В единственной строке выведите два целых числа — сумму в долларах США и белорусских рублях, которую придется оплатить агенству. Поставщик контекстной рекламы выставляет счет по модулю 109 + 7 в качестве скидки на свои услуги.
5
4 2
2 5
3 2
5 1
17 42
