Description

对于一个2行N列的走道。现在用$1*2,2*2$的砖去铺满。问有多少种不同的铺法？（$0\lt n\lt250$）

Format

Input

多组测试数据，每组测试数据包含一个整数n

Output

对于每组测试数据，输出一个整数，表示方案数（要用高精度）

Samples

2
8
12

3
171
2731

Limitation

1s, 1024KiB for each test case.