У Makoto есть большая доска, на которой изначально написано целое положительное число \(n\). После этого он ровно \(k\) раз проделает следующую операцию:
Предположим, что число, записанное сейчас на доске, равно \(v\). Тогда он выберет случайным образом один из делителей \(v\) (включая \(1\) и \(v\)) и заменит \(v\) на этот делитель. Так как Makoto использует свой известный генератор случайных чисел (rng) и число \(58\) как сид этого генератора, то все делители имеют одинаковую вероятность выбора.
Makoto интересуется, чему равно математическое ожидание числа, записанного на доске после всех \(k\) операций.
Можно показать, что это число можно представить как \(\frac{P}{Q}\), где \(P\) и \(Q\) взаимно просты и \(Q \not\equiv 0 \pmod{10^9+7}\). Выведите значение \(P \cdot Q^{-1}\) по модулю \(10^9+7\).
Выходные данные
Выведите одно целое число, математическое ожидание числа записанного на доске после \(k\) операций как \(P \cdot Q^{-1} \pmod{10^9+7}\), где \(P\) и \(Q\) определены выше.
Примечание
В первом примере после одного шага число, записанное на доске, равно \(1\), \(2\), \(3\) или \(6\) с равной вероятностью. Тем самым ответ равен \(\frac{1+2+3+6}{4}=3\).
Во втором примере ответ равен \(1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 1
|
3
|
|
2
|
6 2
|
875000008
|
|
3
|
60 5
|
237178099
|