Filling Shapes

Time limit1sMemory limit1024 MB

Summary

Count the ways to fill a 3 by n grid of tiles with the shape from the picture, with no gaps and no overlaps, for n up to 60.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You have a given integer $n$ . Find the number of ways to fill all $3 \times n$ tiles with the shape described in the picture below. Upon filling, no empty spaces are allowed. Shapes cannot overlap.

This picture describes when $n = 4$ . The left one is the shape and the right one is $3 \times n$ tiles.

Input

The only line contains one integer $n$ ( $1 \le n \le 60$ ), the length.

Output

Print the number of ways to fill.

Hint

In the first example, there are $4$ possible cases of filling.

In the second example, you cannot fill the shapes in $3 \times 1$ tiles.

Examples2

Example 1
Input
```
4
```
Expected output
```
4
```
Example 2
Input
```
1
```
Expected output
```
0
```