Onix

Time limit30sMemory limit1024 MB

Summary

Count the paths that visit every cell of an N by N grid exactly once, starting at the top-left cell and ending at the bottom-left cell, for N up to 8.

Level: Medium6 of 10
Topics: Backtracking, Dynamic programming, Matrix
Solved: No attempts yet

Problem

Everyone knows that Onix, the rock snake from the Pokémon series and games, hides back inside its Poké Ball after every battle. Less is known about what the ball looks like inside. Professor Oak has found that the inside of Onix's ball can be pictured as a square into which Onix coils itself. Depending on Onix's level, it may need more or less room, so there are different ways to coil.

An Onix of level $N$ has a body of $N^2$ segments. The square is divided into $N \times N$ small cells. Onix coils so that consecutive segments of its body are always in adjacent cells, its head is always in the top-left cell, and its tail tip is always in the bottom-left cell. The figure below shows one way a level 3 Onix can fit into the ball.

Sometimes Onix's back starts to hurt, and it changes position. The task is to find how many different positions an Onix of level $N$ can take.

Input

The input is a single line containing Onix's level $N$ ( $1 \le N \le 8$ ).

Output

Print a single integer on one line: the number of different possible positions of an Onix of level $N$ .

Examples1

Example 1
Input
```
3
```
Expected output
```
2
```