Filling Shapes

1000ms

262144K

Description:

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.

$\text{[math]}$ 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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1182A