Unsolvable

Consider the following equation: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: z ₁, z ₂, z ₃, and so on (z _i < z _i + 1). Your task is: given the number n, find the number z _n.

Input

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

Output

Print a single integer — the number z _n modulo 1000000007 (10⁹ + 7). It is guaranteed that the answer exists.

Examples

input

1

output

1

input

2

output

3

input

3

output

15

Solution:

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>

using namespace std;

const int md = 1000000007;

int a[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};

int main() {
//  freopen("in","r",stdin);
//  freopen("out","w",stdout);
int n;
scanf("%d",&n);
int x = 1;
for (int i=1;i<a[n-1];i++) {
    x *= 2;
    if (x >= md) x -= md;
}
printf("%d\n",(x+md-1) % md);
return 0;
}