"Beautiful" permutations

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

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

Your task is to determine the number of good permutations for a given number n.

Input consists of a single integer n (2 ≤ n ≤ 30).

Output should be the number of good permutations of the numbers from 1 to n.

Examples