题目描述

​ 有2xn的一个长方形方格，要用若干1x2的骨牌铺满方格。例如，n=3时，为2x3方格，此时用3个1x2的骨牌铺满方格，共有3种铺法，见图。

输入格式

​一行一个正整数n。

输出格式

一行一个正整数m,即铺法数量。

样例数据

input

3

output

3

数据规模与约定

1≤n≤30

时间限制：$1 \text{s}$

空间限制：$64 \text{MB}$