Magic Sequence

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

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

Each element of the magic sequence is one of the integers from $\{1, 2, \dots, N\}$ ~\{1, 2, \dots, N\}~.
The elements in the magic sequence are in strictly increasing order.
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\}$ ~\{1, 2, \dots, N\}~.

Input Specification

The first line will contain an integer $N$ ~N~.

Output Specification

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

Constraints

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

Sample Input 1

Sample Output 1

Explanation for Sample 1

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

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

32951280098

Comments

There are no comments at the moment.