CodeForces - 225E：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: 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

題意

求出第k個滿足表達式條件的z。z為正整數，x,y不是整數。

思路

這個公式是真的想不到，規律不好找，但是找到了就很簡單。公式是

z=2^k-1

，其中k是梅森素數，要用到快速幂。

AC代碼

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int p[] = {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 n;
int main()
{
    scanf("%d",&n);
    int r=1;
    for(int i=1;i<p[n-1];i++)r=(2*r)%mod;
    printf("%d\n",(r-1+mod)%mod);
    return 0;
}