编程题：铺满方格

有一个1×n的长方形，由边长为1的n个方格构成，例如，当n=3时为1×3的方格长方形如下图所示。求用1×1、1×2、1×3的骨牌铺满方格的方案总数。


### 输入格式:
测试数据有多组，处理到文件尾。每组测试输入一个整数n（1≤n≤50）。

### 输出格式:
对于每组测试，输出一行，包含一个整数，表示用骨牌铺满方格的方案总数。

### 输入样例:
in
3



### 输出样例:
out
4



### 来源：
[1] 黄龙军, 等. 大学生程序设计竞赛入门—C/C++程序设计（微课视频版）, 北京:清华大学出版社, 2020.11. ISBN:9787302564744
[2] 黄龙军.程序设计竞赛入门（Python版）,北京:清华大学出版社,2021.4. ISBN:9787302571230





答案：若无答案欢迎评论