Description

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

Input

一个整数N，N<=1000。

Output

共有多少种铺法。

Sample Input

30

Sample Output

715827883

HINT

Source

NBU OJ