E. Неразрешимость
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Рассмотрим уравнение

где записью [a] обозначается целая часть числа a.

Найдем все целые z (z > 0), при которых это уравнение неразрешимо в целых положительных числах. Выражение «неразрешимо в целых положительных числах» означает, что не существует таких целых положительных чисел x и y (x, y > 0), при которых выполняется описанное выше равенство.

Выпишем все такие z в порядке возрастания: z1, z2, z3, и так далее (zi < zi + 1). От вас требуется по числу n найти число zn.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 40).

Выходные данные

Выведите единственное целое число — остаток от деления числа zn на 1000000007 (109 + 7). Гарантируется, что ответ существует.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
3
Входные данные
3
Выходные данные
15