Вам задано дерево, состоящее из \(n\) вершин. Вы должны сопоставить каждому из \(n-1\) ребер этого дерева целое число таким образом, чтобы выполнялись следующие условия:
- каждое число должно быть целым и строго больше \(0\);
- произведение всех \(n-1\) чисел должно быть равно \(k\);
- количество \(1\)-ц среди всех \(n-1\) чисел должно быть минимально возможным.
Назовем \(f(u,v)\) сумму чисел на простом пути из вершины \(u\) в вершину \(v\). Также, назовем \(\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)\) как индекс распределения дерева.
Определите максимально возможный индекс распределения, который можно получить. Так как ответ может быть слишком большим, выведите его по модулю \(10^9 + 7\).
В данной задаче, так как число \(k\) может быть слишком большим, задана факторизация \(k\) на простые числа.
Выходные данные
Выведите максимально возможный индекс распределения. Так как ответ может быть слишком большим, выведите его по модулю \(10^9+7\).
Примечание
В первом наборе входных данных, один из возможных ответов изображен на рисунке ниже:
В данном случае, \(f(1,2)=1\), \(f(1,3)=3\), \(f(1,4)=5\), \(f(2,3)=2\), \(f(2,4)=4\), \(f(3,4)=2\), и сумма этих \(6\) чисел равна \(17\).
Во втором наборе входных данных, один из возможных ответов изображен ниже:
В этом случае, \(f(1,2)=3\), \(f(1,3)=1\), \(f(1,4)=4\), \(f(2,3)=2\), \(f(2,4)=5\), \(f(3,4)=3\), и сумма этих \(6\) чисел равна \(18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
|
17
18
286
|