Diễn giải: Nhập vào số nguyên dương n. In số Fibonacci thứ n.

✓ Số Fibonacci là một dãy số vô hạn trong đó mỗi số Fibonacci là tổng của hai số trước đó trong dãy. Dãy bắt đầu bằng hai số 0 và 1, sau đó mỗi số tiếp theo là tổng của hai số ngay trước nó.

✓ Dãy Fibonacci thường được định nghĩa bằng công thức sau: F(n) = F(n - 1) + F(n - 2) với F(0) = 0 và F(1) = 1.

Ví dụ: ✓ F(2) = F(1) + F(0) = 1 + 0 = 1; ✓ F(3) = F(2) + F(1) = 1 + 1 = 2; ✓ F(4) = F(3) + F(2) = 2 + 1 = 3;

✓ Dãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Input: Dòng một là số nguyên n (0 < n <= 50).

Output: Số Fibonacci thứ n.

Ví dụ:

Input 9

Output 34

Input 5

Output 5