Số fibonacci.

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Dãy số fibonacci là dãy số thỏa mãn : F1=0, F2=1, Fn=Fn-1+Fn-2. Hãy tìm số Fibonacci thứ n sử dụng đệ quy.

Input

Số nguyên dương n.(1≤n≤20)

Output

In ra số Fibonacci thứ n.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

2

Output

1

Thông tin học tập

• Buổi: B13
• Concepts: recursion, base cases, call stack, fundamental problem-solving
• Giới hạn kiến thức: B01-B13
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10