[Seoul 2007]Tile走道铺砖 查看提交统计提问
总时间限制: 20000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
还是传统的走道铺砖问题，还是2行N列，现在给你三种砖，其规格分别为12,21,2*2。现在用这三种砖将走道铺满且砖与砖块之间不能重叠。问有多少种做法，值得注意的是：如果一种铺放的方法可以由另一个翻转过来得到则这两种只视为一种放法

输入
现给出N的值，请问有多少种不同的放法

输出
如题

样例输入
Sample input 1
2

Sample input 2 4 样例输出
Sample output 1
3
Sample output 2
8
提示 100%的数据,N<=10000