Dãy Fibonacci: ~F_0 = 0~, ~F_1 = 1~, ~F_k = F_{k-1} + F_{k-2}~ với ~k \ge 2~. Hãy cài đặt hàm đệ quy fib(n) theo đúng định nghĩa này và tính ~F_n~.

Dữ liệu vào

Một số nguyên ~n~ (~0 \le n \le 30~).

Kết quả

In ra giá trị của ~F_n~.

Ví dụ

Ví dụ 1

Input:

6

Output:

8

Ví dụ 2

Input:

10

Output:

55

Giải thích

Dãy là 0 1 1 2 3 5 8 ... nên ~F_6 = 8~. Cách viết đệ quy thuần túy này gọi hàm lặp lại rất nhiều lần, vì vậy chỉ dùng được với ~n~ nhỏ (đó là lý do giới hạn ~n \le 30~).