描述

用$2\times1$或$2\times2$的瓷砖铺满一个$2\times n$的矩形，共有多少种不同的铺法呢？ 这里有一个铺满$2\times17$矩形的示例。

输入

输入是一系列的行，每行包含一个整数$n$，满足$0 \leq n \leq 250$。

输出

对于输入的每一行，在单独的一行中输出一个整数，表示铺满$2\times n$矩形的可能铺法的数量。

输入数据1

2
8
12
100
200

输出数据1

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

来源

阿尔伯塔大学本地竞赛 2000年10月14日