题目描述

有$2*n$的一个长方形方格，用一个$1*2$的骨牌铺满方格，对于给出的任意一个$n（1<=n<=46）$，输出铺法的总数。

输入格式

输入一个整数$n$， 表示有2*n的方格

输出格式

一个整数输出方案数

输入样例#1

1

输出样例#1

1

输入样例#2

3

输出样例#2

3