Six
European Junior Olympiad in Informatics 2017
Time Limit: 0.7s, Memory Limit: 64MiB
Ели изследва свойствата на цялото число N. До сега тя е открила, че то има не повече от шест различни прости делителя.

Сега момичето запълва времето си по следния начин. Започвайки с празен списък, Ели записва делители на N, по-големи или равни на две. Добавяйки ново число, тя внимава то да има общи делители (по-големи или равни на две) с най-много едно от вече записаните.

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

Сега Ели се чуди колко на брой са различните валидни последователности от делители на N. Считаме две последователности за различни, ако имат различна дължина, или имат позиция, в която записаните числа са различни.
Вход
На стандартния вход ще бъде зададено цялото число N.
Изход
На стандартния изход изведете едно цяло число – броя различни последователности от делители на N, които Ели би могла да запише. Тъй като резултатът може да бъде много голям, вместо самото число, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N ≤ 1015
  • N ще има не повече от 6 различни прости делителя
Примерен Вход Примерен Изход
628
20302133628
60357056536907882
12156144104757552
Всички 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, но тъй като трябва да изведете само остатъка му по модул 1,000,000,007, резултатът е 14104757650 % 1000000007 = 104757552.
Мрън!