For each integer ~N~, a magic sequence from ~\{1, 2, \dots, N\}~ is defined to be a sequence that satisfies the following conditions:

1. Each element of the magic sequence is one of the integers from ~\{1, 2, \dots, N\}~.
2. The elements in the magic sequence are in strictly increasing order.
3. The elements in odd numbered positions are odd and the elements in even numbered positions are even.

Write a program to find the number of magic sequences from ~\{1, 2, \dots, N\}~.

Input Specification

The first line will contain an integer ~N~.

Output Specification

Output one integer, the number of magic sequences from ~\{1, 2, \dots, N\}~. The output will always be under ~2^{63}-1~.

Constraints

Subtask	Points	Additional constraints
~1~	~10~	~N \le 7~
~2~	~20~	~N \le 20~
~3~	~20~	~N \le 30~
~4~	~50~	~N \le 90~

Sample Input 1

4

Sample Output 1

7

Explanation for Sample 1

There are ~7~ magic sequences: ~[1]~, ~[1, 2]~, ~[3]~, ~[1, 2, 3]~, ~[1, 4]~, ~[3, 4]~, ~[1, 2, 3, 4]~.

Sample Input 2

10

Sample Output 2

143

Sample Input 3

50

Sample Output 3

32951280098