SPOJ in Gyumri

   A long band of fabric is about to be embroidered with a geometric pattern. The hori- zontally-oriented band is marked with a 1xn guiding grid. The pattern is made according to the following rules.

1. The pattern starts in the lower left corner.

2. Every stitch connects two corners of a square in the guiding grid. The stitch may go in any direction: vertical, horizontal, or diagonal.

3. The fabric may be punctured only at the corners of grid squares, and only once for each corner. The final pattern must use all the corners.

4. The embroidery is done with a single continuous thread starting in the lower left corner of the grid and ending in any corner of any square.

   Your task is to write a program that determines the number of different ways to em- broider a band of size 1xn.

   The figure below demonstrates all the 20 ways to embroider a 1x2 band according to the above rules. Front and back stitches are shown with lines of different thickness.

Limitations

   1 ≤ n ≤ 30.

Input

   The input file contains a single integer n.

Output

   The output file should contain a single integer, the number of possible designs.

Example