题目描述

请你用递归的方式求出斐波那契数列的第$n$项，下标从1开始。

斐波那契数列：1,1,2,3,5…，这个数列从第 3项开始，每一项都等于前两项之和

输入描述

共一行，包含整数$n(1\le n\le 30)$。

输出描述

共一行，包含一个整数，表示斐波那契数列的第$n$项。

样例

输入

4

输出

3