Шість
Еллі досліджує властивості заданого цілого числа . Вона вже з'ясувала, що це число має не більше шести різних простих дільників. Просте число — це натуральне число більше , яке не має додатних дільників, окрім і самого себе.
Зараз Еллі займається наступним: починаючи з порожнього списку, вона записує дільники числа , які більші за (деякі дільники можуть повторюватися кілька разів). Додаючи нове число в список, вона стежить за тим, щоб воно мало спільні дільники більше не більше ніж з одним із уже записаних чисел.
Наприклад, якщо число дорівнює , можливі правильні послідовності, які Еллі може створити, це: , , , , , і . Неправильна послідовність, наприклад, , оскільки не є дільником , або , оскільки має спільні дільники і з , і з .
Еллі тепер цікаво, скільки існує різних допустимих послідовностей із дільників числа . Дві послідовності вважаються різними, якщо вони мають різну довжину або є позиція, в якій вони містять різні числа.
Напишіть програму, яка допоможе Еллі визначити кількість допустимих послідовностей із дільників числа .
Вхідні дані
Одне ціле число . Число має не більше різних простих дільників.
Вихідні дані
Виведіть одне ціле число — кількість різних послідовностей дільників числа , які могла б написати Еллі. Оскільки це число може бути великим, виведіть тільки його залишок від ділення на .
Приклади
Пояснення до першого тесту. Нижче наведено всі допустимих послідовностей: , , , , , , , , , , , , , , , , , , , , , , , , , , , .
Пояснення до четвертого тесту. Відповідь , але оскільки відповідь слід обчислити за модулем , то відповідь дорівнює .