#include <bits/stdc++.h>
#pragma comment(linker, "/stack:100000000")
using namespace std;
int a[41];
const int M = (int)1e9 + 7;
int main() {
  a[1] = 1;
  a[2] = 2;
  a[3] = 4;
  a[4] = 6;
  a[5] = 12;
  a[6] = 16;
  a[7] = 18;
  a[8] = 30;
  a[9] = 60;
  a[10] = 88;
  a[11] = 106;
  a[12] = 126;
  a[13] = 520;
  a[14] = 606;
  a[15] = 1278;
  a[16] = 2202;
  a[17] = 2280;
  a[18] = 3216;
  a[19] = 4252;
  a[20] = 4422;
  a[21] = 9688;
  a[22] = 9940;
  a[23] = 11212;
  a[24] = 19936;
  a[25] = 21700;
  a[26] = 23208;
  a[27] = 44496;
  a[28] = 86242;
  a[29] = 110502;
  a[30] = 132048;
  a[31] = 216090;
  a[32] = 756838;
  a[33] = 859432;
  a[34] = 1257786;
  a[35] = 1398268;
  a[36] = 2976220;
  a[37] = 3021376;
  a[38] = 6972592;
  a[39] = 13466916;
  a[40] = 20996010;
  int n;
  cin >> n;
  n = a[n];
  int res = 1;
  for (int i = 1; i <= n; i++) {
    res *= 2;
    res %= M;
  }
  res = (res + M - 1) % M;
  cout << res;
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma comment(linker, "/stack:100000000")
using namespace std;
int a[41];
const int M = (int)1e9 + 7;
int main() {
  a[1] = 1;
  a[2] = 2;
  a[3] = 4;
  a[4] = 6;
  a[5] = 12;
  a[6] = 16;
  a[7] = 18;
  a[8] = 30;
  a[9] = 60;
  a[10] = 88;
  a[11] = 106;
  a[12] = 126;
  a[13] = 520;
  a[14] = 606;
  a[15] = 1278;
  a[16] = 2202;
  a[17] = 2280;
  a[18] = 3216;
  a[19] = 4252;
  a[20] = 4422;
  a[21] = 9688;
  a[22] = 9940;
  a[23] = 11212;
  a[24] = 19936;
  a[25] = 21700;
  a[26] = 23208;
  a[27] = 44496;
  a[28] = 86242;
  a[29] = 110502;
  a[30] = 132048;
  a[31] = 216090;
  a[32] = 756838;
  a[33] = 859432;
  a[34] = 1257786;
  a[35] = 1398268;
  a[36] = 2976220;
  a[37] = 3021376;
  a[38] = 6972592;
  a[39] = 13466916;
  a[40] = 20996010;
  int n;
  cin >> n;
  n = a[n];
  int res = 1;
  for (int i = 1; i <= n; i++) {
    res *= 2;
    res %= M;
  }
  res = (res + M - 1) % M;
  cout << res;
  return 0;
}

```