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.
A single integer (2 \leq n \leq 30).
Output the number of good permutations of the numbers from to .
Example 1