跳至正文
题库3200
#3200

Unsolvable

查看题目操作

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

1
1
2
3
3
15