Fibonacci

Cho một số nguyên dương \(n\) \((1 \leq n \leq 30)\).

Hãy viết một hàm đệ quy để tính số Fibonacci thứ \(n\), với quy ước:

Input

Một số nguyên \(n\).

Output

In ra giá trị \(F(n)\).

Sample Input 1

4

Sample Output 1

3

Sample Input 2

5

Sample Output 2

5