Задача 71. О, числа! ≡

Условие

Я всматриваюсь в вас, о, числа,

И вы мне видитесь одетыми в звери, в их шкурах,

Рукой опирающимися на вырванные дубы.

Вы даруете единство между змееобразным движением

Хребта вселенной и пляской коромысла,

Вы позволяете понимать века, как быстрого хохота зубы.

Мои сейчас вещеобразно разверзлися зеницы

Узнать, что будет Я, когда делимое его — единица.

Велимир Хлебников, "Числа", 1912 г.

Велимир занят серьёзным математическим исследованием: из имеющихся на доске чисел он выбирает наибольшее, стирает его и добавляет два новых числа — это наибольшие делители того числа, которое сейчас исчезло, но не равные ему. Например, если наибольшее из чисел на доске сейчас 100, то вместо него появятся числа 50 и 25, а если это число 4, то вместо него появятся числа 2 и 1.

Если же наибольшее из оставшихся чисел — простое, то Велимир запишет вместо него один делитель — единицу. Единицы Велимир не изменяет.

Сколько всего единиц окажется на доске, если изначально на ней было написано число 10ⁿ?

Формат входных данных

Единственная строка входного файла содержит неотрицательное целое число n.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

0 ≤ n ≤ 40

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере n = 0. 10⁰ = 1. Велимир не изменяет единицы, она останется на доске.

Во втором примере n = 2. 10² = 100. Велимир будет получать следующие наборы чисел:

1) 50, 25;

2) 25, 10, 25;

3) 5, 1, 10, 25;

4) 5, 1, 10, 5, 1;

5) 5, 1, 2, 5, 5, 1;

6) 1, 1, 2, 5, 5, 1;

7) 1, 1, 2, 1, 5, 1;

8) 1, 1, 2, 1, 1, 1;

9) 1, 1, 1, 1, 1, 1.

Всего шесть единиц.

Примеры тестов

0

1

2

6