Combinatorics is one of the most complicated areas of mathematics. Fortunately informatics has enabled mathematicians to calculate large amounts of complex data in much shorter times. Pr. Green, who isn't very creative, needs to solve a problem:

We have the set of numbers from 1 to n, and we have to prepare the permutations of the numbers from 1 to n in such a way that if we call the permutation a1, a2,...,an; we take any two numbers from the set ai and aj, where i < j, then ai + i ≤ aj + j.

Question: How many permutations are there complying the given criteria?

Input specification
You will be given an integer (n) which determines the range from 1 to n where n ≤ 20

Output specification
The number of the possible combinations that follow this condition.

Explanation:
There are 4 cases possible here:

• 3,2,1 (since 3+1 ≤ 2+2 ≤ 1+3)
• 1,3,2 (since 1+1 ≤ 3+2 ≤ 2+3)
• 1,2,3 (since 1+1 ≤ 2+2 ≤ 3+3)
• 2,1,3 (since 2+1 ≤ 1+2 ≤ 3+3)