"Beautiful" permutations#415

"Beautiful" permutations

1 second
64 megabytes
Easy

A permutation of the integers from to is called good if and only if the absolute values of the differences between each pair of consecutive numbers form a permutation of the integers from to n - 1.

For example, the permutation is not good, because the absolute differences are , which do not form a permutation of to . However, the permutation is good, because the differences form a valid permutation.

In this problem, you are given an integer , and you are required to find the number of good permutations of numbers.

Input

A single integer (2 \leq n \leq 30).

Output

Output the number of good permutations of the numbers from to .

Examples

Example 1

Loading
Loading