题目描述

现有2×1大小的瓷砖若干个，现在要使用这些瓷砖来铺一条宽度为3，长为n的小路，请问一共有多少种贴法？

例如n=2时,为3 × 2方格，骨牌的铺放方案有三种,如下图：

输入格式

输入有多组测试数据，每组测试数据包含一个整数n

输出格式

每组测试数据输出1个整数，表示当前长度的小路的贴法总数。

样例

输入样例#1：

2
8
12

输出样例#1：

3
153
2131

数据范围与提示

数据范围：

1<=N<=30