考虑以下等式:
$$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