Description

工匠要铺一条宽 3 格、长 N 格的长方形走廊地面，地砖只有两种：

2×2 正方形地砖（占 2 行 2 列）

1×1 正方形地砖（占 1 行 1 列）

要求：地砖不重叠、不切割、完全铺满 3×N 区域，问：有多少种不同铺法？

Format

Input

一行一个整数n(n<=40)

Output

根据题意输出

Samples

1

1

2

3

Limitation

1s, 1024KiB for each test case.