In order for the spacecraft to take off, each crew member must be given a ticket. Each ticket must have a sequence of n digits, where n is an even positive number.

Daniel considers a ticket to be super happy if two properties are true:

• The sum of the first n digits is equal to the sum of the last n digits.
• The sum of digits in even positions is equal to the sum of digits in odd positions. Help Daniil count the number of different super lucky tickets.

Input

The first line contains one number n (2 ≤ n ≤ 6) - the length of the ticket. It is guaranteed that n is even.

Output

Print the number of super lucky tickets of length n.