2. Weights Again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While creating tests for the previous problem, the jury pondered the question: how many different tests can be devised for a given $$$k$$$? The jury considers two tests to be different if one cannot be obtained from the other by swapping groups and/or permuting numbers within the groups. Write a program to find the answer to this question.

Input

A single integer $$$k$$$ ($$$1 \le k \le 16$$$) is given.

Output

Output a single integer — the number of ways to split the first $$$4 \cdot k$$$ natural numbers into two groups of $$$2 \cdot k$$$ numbers each, such that the sums of the numbers in the groups are equal.

Example
Input
2
Output
4
Note

For the example with $$$k=2$$$, there are 4 different ways to partition:

  • 1 2 7 8 and 3 4 5 6
  • 1 3 6 8 and 2 4 5 7
  • 1 4 5 8 and 2 3 6 7
  • 1 4 6 7 and 2 3 5 8

Grading System. Solutions that work correctly for $$$k \le 6$$$ will be awarded 50 points.

Note: The answer may not fit in a 32-bit integer type; it is recommended to use a 64-bit type (long long in C++, long in Java and C#, int64 in Pascal). In Python, no additional steps are required.