#include <bits/stdc++.h>
using namespace std;
long long func(long long a, long long b) {
  long long int res = 1;
  while (b) {
    if (b % 2) res = (res * a) % 1000000007;
    a = (a * a) % 1000000007;
    b /= 2;
  }
  return (res % 1000000007 + 1000000006) % 1000000007;
}
int main() {
  int L[40] = {1,       2,       3,       6,       8,      9,      15,
               30,      44,      53,      63,      260,    303,    639,
               1101,    1140,    1608,    2126,    2211,   4844,   4970,
               5606,    9968,    10850,   11604,   22248,  43121,  55251,
               66024,   108045,  378419,  429716,  628893, 699134, 1488110,
               1510688, 3486296, 6733458, 10498005};
  int n;
  cin >> n;
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  } else {
    cout << func(4, L[n - 2]) << endl;
    return 0;
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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 func(long long a, long long b) {
  long long int res = 1;
  while (b) {
    if (b % 2) res = (res * a) % 1000000007;
    a = (a * a) % 1000000007;
    b /= 2;
  }
  return (res % 1000000007 + 1000000006) % 1000000007;
}
int main() {
  int L[40] = {1,       2,       3,       6,       8,      9,      15,
               30,      44,      53,      63,      260,    303,    639,
               1101,    1140,    1608,    2126,    2211,   4844,   4970,
               5606,    9968,    10850,   11604,   22248,  43121,  55251,
               66024,   108045,  378419,  429716,  628893, 699134, 1488110,
               1510688, 3486296, 6733458, 10498005};
  int n;
  cin >> n;
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  } else {
    cout << func(4, L[n - 2]) << endl;
    return 0;
  }
  return 0;
}

```