题目描述

一天，晨晨的数学老师布置了一道题目，大意如下：用 1×1 和 2×2 的磁砖不重叠地铺满 n×3 的地板，共有多少种方案？

例如：

1. n=1 时：1×3的地板方法就一个，直接由三个1×1的磁砖铺满。

2. n=2 时：2×3的地板可以由下面3种方案铺满：

输入格式

一行：一个整数 n 。

数据范围

1 ≤ n ≤ 50

输出格式

输出铺满 n×3 的地板的方案数。

样例

3

5