题目描述

对于一个2行N列的走道。现在用1*2或2*2的砖去铺满。问有多少种不同的方式（请用递推方式求解）。如果N很大，需要高精度计算。下图是一个2行17列的走道的某种铺法：

输入要求

一个整数N，N<=1000。

输出要求

共有多少种铺法。

输入样例

30

输出样例

715827883

提示

来源

NBU OJ