← 返回题目列表

Codeforces · 225/E

E. 无法解决

中文机器翻译题面 查看原题

考虑以下等式:

$$z = \left\lfloor \frac{x}{2} \right\rfloor + y + xy$$

让我们找到所有整数 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

输出 #1

1

输入 #2

2

输出 #2

3

输入 #3

3

输出 #3

15