Рассмотрим уравнение
где записью
[a] обозначается целая часть числа
a.
Найдем все целые z (z > 0), при которых это уравнение неразрешимо в целых положительных числах. Выражение «неразрешимо в целых положительных числах» означает, что не существует таких целых положительных чисел x и y (x, y > 0), при которых выполняется описанное выше равенство.
Выпишем все такие z в порядке возрастания: z1, z2, z3, и так далее (zi < zi + 1). От вас требуется по числу n найти число zn.
Выходные данные
Выведите единственное целое число — остаток от деления числа zn на 1000000007 (109 + 7). Гарантируется, что ответ существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
3
|
|
3
|
3
|
15
|