题目描述

小青在学习递归，他想用递归来计算斐波那契数列。

斐波那契数列：1, 1, 2, 3, 5, 8, 13... 从第三项开始，每一项都等于前两项之和。

请你帮助小青用递归的方法计算第 n 项斐波那契数。

输入格式

输入一个正整数 n

输出格式

输出第 n 项斐波那契数

样例

样例 1

输入 #1

7

输出 #1

13

提示

递归公式：F(n) = F(n-1) + F(n-2)，F(1) = 1, F(2) = 1