3481: Unsolvable
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
time limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputConsider the following equation:
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