Шесть
Шесть
Элли изучает свойства некоторого заданного целого числа 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.
6
28
203021
33628
60357056536
907882
12156144
104757552