#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
long long int s[40] = {
    2,      3,       5,       7,       13,      17,      19,       31,
    61,     89,      107,     127,     521,     607,     1279,     2203,
    2281,   3217,    4253,    4423,    9689,    9941,    11213,    19937,
    21701,  23209,   44497,   86243,   110503,  132049,  216091,   756839,
    859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011};
void solve(int n) {
  int i, j, x, y, z = 0, lc, lv, tw, th;
  long long int a = 1;
  if (n == 1) {
    printf("1\n");
    return;
  }
  n--;
  s[n]--;
  s[n] %= mod - 1;
  for (i = 30; i >= 0; i--) {
    a = (a * a) % mod;
    if (((1 << i) & s[n]) > 0) a = (a * 2) % mod;
  }
  printf("%I64d\n", (a - 1 + mod) % mod);
}
int main() {
#pragma comment(linker, "/STACK:268435456")
  int n, m, k;
  while (scanf("%d", &n) != EOF) solve(n);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Consider the following equation: 

<image> where sign [a] represents the integer part of number a.

Let's find all integer z (z > 0), for which this equation is unsolvable in positive integers. The phrase "unsolvable in positive integers" means that there are no such positive integers x and y (x, y > 0), for which the given above equation holds.

Let's write out all such z in the increasing order: z1, z2, z3, and so on (zi < zi + 1). Your task is: given the number n, find the number zn.

Input

The first line contains a single integer n (1 ≤ n ≤ 40).

Output

Print a single integer — the number zn modulo 1000000007 (109 + 7). It is guaranteed that the answer exists.

Examples

Input

1


Output

1

Input

2


Output

3

Input

3


Output

15

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
long long int s[40] = {
    2,      3,       5,       7,       13,      17,      19,       31,
    61,     89,      107,     127,     521,     607,     1279,     2203,
    2281,   3217,    4253,    4423,    9689,    9941,    11213,    19937,
    21701,  23209,   44497,   86243,   110503,  132049,  216091,   756839,
    859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011};
void solve(int n) {
  int i, j, x, y, z = 0, lc, lv, tw, th;
  long long int a = 1;
  if (n == 1) {
    printf("1\n");
    return;
  }
  n--;
  s[n]--;
  s[n] %= mod - 1;
  for (i = 30; i >= 0; i--) {
    a = (a * a) % mod;
    if (((1 << i) & s[n]) > 0) a = (a * 2) % mod;
  }
  printf("%I64d\n", (a - 1 + mod) % mod);
}
int main() {
#pragma comment(linker, "/STACK:268435456")
  int n, m, k;
  while (scanf("%d", &n) != EOF) solve(n);
  return 0;
}

```