题目描述

为了美化环境，市长提出全民种花活动：第一户种1盆，第二户种1盆，第三户种2盆，第四户种3盆，第五户种5盆，第六户种8盆……以此类推，请问第n户要种多少盆？

输入格式

1个整数n，代表第几户(n＜1000)。

输出格式

1个整数，代表第n户要种花的盆数。

样例

10

55

提示

根据题意，可以得出以下规律：第1个数是1，第2个数是1，从第3个开始，每个数等于前两个数之和，这就是著名的菲波那契数列。