Задача Azs. У країні є N міст, які з’єднані між собою дорогами так, що із кожного міста у кожне місто можна потрапити лише одним маршрутом, а на кожній дорозі, там де вона входить в місто збудовано АЗС (тобто, якщо  місто сполучене з іншими містами трьома дорогами, то АЗС теж 3). Король країни вирішив, що бюджет дозволяє побудувати ще М нових міст, і, відповідно, М доріг. Причому початкові умови про один маршрут між будь-якою парою міст та кількість АЗС відповідно кількості доріг потрібно було зберегти. Придворний програміст написав програму, яка може рахувати добуток кількостей усіх АЗС (тобто знаходить число (АЗС_{(першого_міста)} х АЗС_{(другого_міста)} х … АЗС_{(N-1_міста)} х АЗС _{(N_міста)} ). Допоможіть Придворному Будівельному Управлінню побудувати міста і дороги таким чином, аби результатом роботи програми Придворного Програміста було максимальне число.

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

Приклади