B. Bad Sindibad
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After his seven great voyages and accumulating unimaginable wealth, Sindibad had many servants, from humans to Jinns, some of whom he tricked many times through his past adventures. They serve him well, so Sindibad refuses to free any of them. However, he becomes wary of their potential rebellion against him. So, he swears to free his Jinn servants if they achieve one task. He wants to give them a task that would seem simple but may take them a long time to finish.

Given a grid of length $$$n$$$ and width $$$4$$$, and this specific shape (shown in the image below), his Jinn servants must tile the entire grid using copies of this shape.

The shape can be rotated or flipped in any way but must completely fit within the grid. Each grid cell must be covered exactly once by a shape (no overlaps or empty cells) and every tile must have an adjacent tile to which they form a rectangle.

Determine how many distinct ways this grid can be fully tiled using copies of this shape.

Input

The input contains a single integer $$$n, ( 1 \leq n \leq 40 )$$$ — the length of the grid.

Output

Output a single integer — the number of distinct ways the shape can be placed within the grid.

Example
Input
3
Output
4