29424번 - Наименьшее общее кратное 다국어

문제

Вася --- юный программист. Он уже умеет решать задачи на графы, структуры данных, комбинаторику и динамическое программирование. Но вот с теорией чисел он еще не знаком. Поэтому он стал посещать лекции по теории чисел. На одном из первых занятий он узнал, что такое наименьшее общее кратное.

Набором чисел назовем множество, в котором элементы могут повторяться.

Наименьшее общее кратное набора $S$ целых положительных чисел --- минимальное положительное целое число, которое делится на каждый элемент набора $S$.

После каждого занятия преподаватель задает домашнее задание по пройденным темам. Вот и в этот раз он задал непростое задание:

Заданы числа $n$ и $k,ドル требуется определить количество таких наборов из $k$ элементов, наименьшее общее кратное которых равно $n$

Например, если $n = 6$ и $k = 2,ドル то подходящие наборы это: $\lbrace 1, 6 \rbrace,ドル $\lbrace 2, 3 \rbrace,ドル $\lbrace 2, 6 \rbrace,ドル $\lbrace 3, 6 \rbrace,ドル $\lbrace 6, 6 \rbrace$. Поэтому ответ будет равен 5. Заметим, что наборы, отличающиеся только порядком элементов, считаются одинаковыми.

Вася очень хорошо усвоил лекцию, а также он очень смышленный мальчик, поэтому он уже решил задачу. Но он не уверен в том, что все сделал правильно. Вася просит вас помочь проверить его программу: решите эту же задачу и найдите ответы на некоторые тесты. Так как ответ может быть очень большим, Вася решил, что ему достаточно буде знать остаток от деления ответа на 10ドル^9+7$.

입력

В первой строке входного файла через пробел заданы числа $n$ (1ドル \le n \le 10^{12}$) и $k$ (1ドル \le k \le 100$).

출력

В выходной файл требуется вывести одно число: ответ по модулю 10ドル^9+7$.

제한

힌트