D. Makoto и доска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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$$$.

Входные данные

Единственная строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^{15}$$$, $$$1 \leq k \leq 10^4$$$).

Выходные данные

Выведите одно целое число, математическое ожидание числа записанного на доске после $$$k$$$ операций как $$$P \cdot Q^{-1} \pmod{10^9+7}$$$, где $$$P$$$ и $$$Q$$$ определены выше.

Примеры
Входные данные
6 1
Выходные данные
3
Входные данные
6 2
Выходные данные
875000008
Входные данные
60 5
Выходные данные
237178099
Примечание

В первом примере после одного шага число, записанное на доске, равно $$$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}$$$.