Bolik reached the museum, the building of which is a square N × N divided into N2 equal square halls. The entrance to the museum is located in the lower left hall, and Lyolik is waiting for Bolik in the upper right. From each hall you can go to the adjacent hall (two halls are called adjacent if they have a common wall).
Now Bolik wants to determine how many possible paths he has to Lelik. Of course, he is only interested in paths of the shortest length.
Input Format
The input is one natural number N (2 ≤ N ≤ 22).
Output format
Print the only natural number — the number of different paths of the smallest length.
Example