Рабочее место участника

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

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

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

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

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

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

В первой строке входного файла через пробел заданы числа `n` (`1\ ≤\ n\ ≤\ 10^{12}`) и `k` (`1\ ≤\ k\ ≤\ 100`). В выходной файл требуется вывести одно число: ответ по модулю `10^9+7`.

6 2

5

239 3

3