06/04/2025 18:15:31

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2167. Наименьшее общее кратное

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

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

Наименьшее общее кратное набора

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

$S$ .

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

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

Например, если

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

Пример ввода 1

6 2

Пример вывода 1

Пример ввода 2

239 3

Пример вывода 2

Источник: neerc.ifmo.ru/school