n×3 瓷砖铺地

题目描述

有一条大小为 $n \times 3$ 的长方形路面（长度为 $n$，宽度为 $3$）。
现在有两种规格的瓷砖：

• 黄色瓷砖：大小为 $1 \times 1$；
• 绿色瓷砖：大小为 $2 \times 2$。

要求使用这两种瓷砖不重叠地铺满整块路面，瓷砖不能超出路面边界。
问一共有多少种不同的铺设方案？

两种铺法只要有某一块瓷砖的位置或朝向不同，就视为不同方案。

例如：

• 当 $n = 1$ 时，只能全部用 $1 \times 1$ 的瓷砖铺满，只有 $1$ 种铺法；
• 当 $n = 2$ 时，可以全部用 $1 \times 1$，也可以在上面或下面放一块 $2 \times 2$，共有 $3$ 种铺法。

输入格式

输入只有一行，包含一个整数 $n$，表示路面的长度。

输出格式

输出一行，一个整数，表示不同的铺设方案数量。

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

2

输出 #2

3

数据范围

对于 $100\%$ 的数据，保证 $1 \le n \le 30$。
结果在 $64$ 位有符号整数范围内。