题目描述

用$2 \times 1$的多米诺骨牌铺满一个$3 \times n$的矩形，共有多少种不同的铺法？

这里有一个$3 \times 12$矩形的一种铺法示例

输入

输入包含若干个测试用例，最后一行包含$-1$表示输入结束。每个测试用例为一行，包含一个整数$0 \leq n \leq 30$。

输出

对于每个测试用例，输出一个整数，表示铺满$3 \times n$矩形的不同铺法的数量。

输入数据示例 1

2  
8  
12  
-1  

输出数据示例 1

3  
153  
2131  

来源

Waterloo 本地赛 2005.09.24