#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7;
inline int f(int x, int y) { return (x >> 1) + y + x * y; }
int solve(int n) {
  vector<long long> ans;
  for (long long i = 1;; ++i) {
    bool flag = false;
    for (long long x = 1; (x >> 1) + 1 + x <= i; ++x) {
      if ((i - (x >> 1)) % (x + 1) == 0 && (i - (x >> 1)) / (x + 1) > 0) {
        flag = true;
        break;
      }
    }
    if (!flag) {
      cout << i << endl;
      ans.push_back(i);
      if (((int)(ans).size()) == 40) break;
    }
  }
  for (int i = (0); i < (((int)(ans).size())); ++i) printf("%lld ", ans[i]);
}
int a[] = {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};
const int P = 1e9 + 7;
int Pow(int x, int y) {
  int r = 1;
  for (int t = y; t; t >>= 1, x = 1ll * x * x % P)
    if (t & 1) r = 1ll * r * x % P;
  return r;
}
int main() {
  int n;
  cin >> n;
  int b = Pow(2, a[n - 1] - 1);
  b--;
  if (b < 0) b += P;
  cout << b << endl;
  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;
const int N = 1e4 + 7;
inline int f(int x, int y) { return (x >> 1) + y + x * y; }
int solve(int n) {
  vector<long long> ans;
  for (long long i = 1;; ++i) {
    bool flag = false;
    for (long long x = 1; (x >> 1) + 1 + x <= i; ++x) {
      if ((i - (x >> 1)) % (x + 1) == 0 && (i - (x >> 1)) / (x + 1) > 0) {
        flag = true;
        break;
      }
    }
    if (!flag) {
      cout << i << endl;
      ans.push_back(i);
      if (((int)(ans).size()) == 40) break;
    }
  }
  for (int i = (0); i < (((int)(ans).size())); ++i) printf("%lld ", ans[i]);
}
int a[] = {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};
const int P = 1e9 + 7;
int Pow(int x, int y) {
  int r = 1;
  for (int t = y; t; t >>= 1, x = 1ll * x * x % P)
    if (t & 1) r = 1ll * r * x % P;
  return r;
}
int main() {
  int n;
  cin >> n;
  int b = Pow(2, a[n - 1] - 1);
  b--;
  if (b < 0) b += P;
  cout << b << endl;
  return 0;
}

```