题目描述

有一个1×n 大小的长方形，用1×1、1×2和1×3大小的骨牌铺满方格（骨牌数量不限），请问有多少种铺法？

例如：当n=3时，为1×3的方格，此时用1×1、1×2和1×3的骨牌铺满方格，共有四种铺法。

输入格式

一个整数n（n<=50）

输出格式

一个整数，表示骨牌的铺法

3

4