Олимпиадный тренинг

Задача . D. Makoto и доска


У 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\) определены выше.

Примечание

В первом примере после одного шага число, записанное на доске, равно \(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
Статистика успешных решений по компиляторам
 Кол-во
С++5