题目描述

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

输入格式

输入一个整数 n，表示有 2×n 的方格。

输出格式

一个整数，表示铺法的总数。

输入样例 #1

1

输出样例 #1

1

输入样例 #2

3

输出样例 #2

3