Элли изучает свойства некоторого заданного целого числа 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.
Одно целое число n (1≤n≤1015). Число n содержит не более 6 различных простых делителей.
Выведите одно целое число — количество различных последовательностей делителей числа n, которые могла бы написать Элли. Поскольку это число может быть большим, выведите только его остаток от деления на 109+7.
Пояснение к первому тесту. Далее перечислены все 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, но поскольку ответ следует вычислить по модулю 109+7, то ответ равен 14104757650 % (109+7)=104757552.