Hardest problem of this contest

Time Limit: 2000 ms

Memory Limit: 65536 ms

Description

给你很多个1*2的长方形(可以旋转)和很多个2*2的正方形,你需要填满一个2*n的长方形。显然随意的摆放都是可行的,所以我很好奇一共有多少种摆放方式。

Input

多case,EOF结束。每个case包含一行,一个整数n。1<=n<=250。

Output

输出可以摆放的种数

Sample Input

1
2

Sample Output

1
3

Hint

以下Hint只有女生能看
作为一位资深的女生部长,hdd想提醒他亲爱的学妹们:这题要写高精度的。

Source

HJWAJ

提交代码