ID: 1032

Type: Default

1000ms

256MiB

Difficulty: 7

Uploaded By:

Tags>

递推

NOI-OJ

基本算法-递归与递推

描述

有 2*n的一个长方形方格，用一个1*2的骨牌铺满方格。编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。

输入

一行是一个整数n（0<n<90)，为2*n的一个长方形方格数。

输出

一行，一个整数，为铺满方格的铺法总数。

样例输入

样例输出