编程题：骨牌铺方格

在2×n的一个长方形方格中，用一个1×2的骨牌铺满方格，输入n，输出铺放方案的总数。例如n=3时，骨牌的铺放方案有3种，如下图所示。


### 输入格式:

测试数据有多组，处理到文件尾。每组测试输入一个整数n（0<n≤50），表示长方形方格的规格是2×n。

### 输出格式:

对于每组测试，请输出铺放方案的总数，每组测试的输出占一行。

### 输入样例:

in
3
50


### 输出样例:

out
3
20365011074


### 出处:
HDOJ 2046





答案：若无答案欢迎评论