ID: 1031

Type: Default

1000ms

128MiB

Difficulty: 6

Uploaded By:

Tags>

递推

NOI-OJ

基本算法-递归与递推

描述

把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。假设这过程中没有兔子死亡，试问第n个月后养殖场中共有多少对兔子。

输入

一行是一个整数n（1<n<90)。

输出

一行，一个整数，为第n个月后养殖场中的兔子数量。

样例输入

样例输出