Задача Azs. У країні є N міст, які з’єднані між собою дорогами так, що із кожного міста у кожне місто можна потрапити лише одним маршрутом, а на кожній дорозі, там де вона входить в місто збудовано АЗС (тобто, якщо місто сполучене з іншими містами трьома дорогами, то АЗС теж 3). Король країни вирішив, що бюджет дозволяє побудувати ще М нових міст, і, відповідно, М доріг. Причому початкові умови про один маршрут між будь-якою парою міст та кількість АЗС відповідно кількості доріг потрібно було зберегти. Придворний програміст написав програму, яка може рахувати добуток кількостей усіх АЗС (тобто знаходить число (АЗС(першого_міста) х АЗС(другого_міста) х … АЗС(N-1_міста) х АЗС (N_міста) ). Допоможіть Придворному Будівельному Управлінню побудувати міста і дороги таким чином, аби результатом роботи програми Придворного Програміста було максимальне число.
Технічні умови. Програма Azs читає із пристрою стандартного введення у першому рядку два цілих числа N і M. Далі N-1 рядок по два числа (1<=a;b<=N) – номери міст, що з’єднані дорогою. Програма виводить максимально можливий добуток кількостей АЗС у кожному з міст по модулю 1000000007. (2<=N<=100000, 0<=M<=100000).
Приклади
| Введення | Виведення |
| 2 1 1 2 |
2 |
| 2 0 1 2 |
1 |