Розмалюйте дерево

Обмеження: 2 сек., 256 МіБ

Сьогодні Зеник хоче подарувати Марічці дерево. Як відомо, дерево — це зв’язний граф, який складається з \(n\) вершин та \(n - 1\) ребра. Та Зеник вирішив, що просте дерево буде не таким цікавим подарунком, як розфарбоване дерево. Усього в нього є \(k\) різних фарб, кожна вершина повинна бути помальована в один із цих кольорів.

Зеник вважає, що дерево розмальоване найцікавіше, якщо відстань між двома найближчими вершинами однакового кольору максимальна. Вам же потрібно допомогти Зенику та знайти цю максимальну відстань та кількість таких найцікавіших розфарбувань дерева. Оскільки ця кількість може бути дуже великою, виведіть її остачу від ділення на просте число \(10^9+7\). Два розфарбування вважаються різними, якщо в них існує хоча б одна вершина, пофарбована в різний колір.

Вхідні дані

У першому рядку задано два цілих числа \(n\) і \(k\) — кількість вершин в дереві і кількість різних фарб, відповідно.

У наступних \(n-1\) рядках задано по два цілих числа \(a_i\), \(b_i\), які означають, що вершина \(a_i\) зв’язана з вершиною \(b_i\).

Вихідні дані

У єдиному рядку виведіть два цілих числа — максимальну відстань між однаковими вершинами та кількість таких розфарбувань по модулю \(10^9+7\).

Обмеження

\(2 \le n \le 2000\),

\(1 \le k < n\),

\(1 \le a_i, b_i \le n\).

Приклади