241786 - 骨牌铺方格
题目描述
有 1 \times n（n \le 50）的一个长方形，用 1 \times 1、1 \times 2 和 1 \times 3 的骨牌铺满方格，请问有多少种铺法？
例如当 n=3 时为 1 \times 3 的方格。此时用 1 \times 1 、1 \times 2 和 1 \times 3 的骨牌铺满方格，共有四种铺法。如下图：
输入
一行，包含一个整数 n（n≤50），表示方格的数量
输出
一行，包含一个整数，表示不同的骨牌铺法数量。
样例
输入
3
输出
4
说明
对于 100% 的数据，保证 1 ≤ n ≤ 50.