eolymp
bolt
Try our new interface for solving problems
Məsələlər

Шесть

Шесть

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Элли изучает свойства некоторого заданного целого числа n. Пока она обнаружила, что оно имеет не более шести различных простых делителей. Простое число — это натуральное число больше 1, которое не имеет положительных делителей, кроме 1 и самого себя.

Сейчас девушка проводит время следующим образом. Начиная с пустого списка, она записывает делители числа n, большие 1 (некоторые делители могут повторяться несколько раз). Добавляя в список новое число, она следит за тем, чтобы оно имело общие делители больше 1 не более чем с одним из уже записанных чисел.

Например, если число n равно 12156144, то возможными правильными последовательностями, которые может сгенерировать девушка, будут (42), (616, 6, 91, 23), (91, 616, 6, 23), (66, 7), (66, 7, 7, 23, 299, 66), (143, 13, 66) и (42, 12156144). Примером неправильной последовательности является (5, 11), так как 5 не является делителем 12156144, или (66, 13, 143), так как 143 имеет общие делители и с 13 и с 66.

Теперь Элли интересно, сколько существует различных допустимых последовательностей из делителей числа n. Мы считаем две последовательности разными, если они имеют разную длину или есть позиция, в которой они имеют разные числа.

Напишите программу, которая поможет Элли найти количество допустимых последовательностей из делителей числа n.

Giriş verilənləri

Одно целое число n~(1 \le n \le 10^{15}). Число n содержит не более 6 различных простых делителей.

Çıxış verilənləri

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

Nümunə

Пояснение к первому тесту. Далее перечислены все 28 допустимых последовательностей: \{(2), (2, 2), (2, 2, 3), (2, 2, 3, 3), (2, 3), (2, 3, 2), (2, 3, 2, 3), (2, 3, 3), (2, 3, 3, 2), (2, 6), (2, 6, 3), (3), (3, 2), (3, 2, 2), (3, 2, 2, 3), (3, 2, 3), (3, 2, 3, 2), (3, 3), (3, 3, 2), (3, 3, 2, 2), (3, 6), (3, 6, 2), (6), (6, 2), (6, 2, 3), (6, 3), (6, 3, 2), (6, 6)\}.

Пояснение к четвертому тесту. Ответ 14104757650, но поскольку ответ следует вычислить по модулю 10^9 + 7, то ответ равен 14104757650~\%~(10^9 + 7) = 104757552.

Giriş verilənləri #1
6
Çıxış verilənləri #1
28
Giriş verilənləri #2
203021
Çıxış verilənləri #2
33628
Giriş verilənləri #3
60357056536
Çıxış verilənləri #3
907882
Giriş verilənləri #4
12156144
Çıxış verilənləri #4
104757552
Mənbə EJOI 2017 День 1 (Первая Европейская Юниорская Олимпиада по Информатике)