Gia tộc thỏ của Bình có đặc tính sinh sản rất thú vị: tháng thứ \(0\) có 0 cặp thỏ, tháng thứ 1 có 1 cặp thỏ. Kể từ tháng thứ 2, số cặp thỏ ở tháng thứ N bằng tổng số cặp thỏ của hai tháng liên tiếp trước đó (tháng \(N-1\) và tháng \(N-2\)).

An thách đố Bình tính nhanh số cặp thỏ ở tháng thứ \(N\) để xem khả năng lập trình của Bình thế nào. Hãy giúp Bình giải bài toán này!

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên duy nhất \(N\) (\(0 \le N $\le 45\)).

Dữ liệu ra

• In ra số nguyên duy nhất là số cặp thỏ ở tháng thứ \(N\).

Ví dụ

Đầu vào:

5

Đầu ra:

5

Giải thích: Dãy số cặp thỏ qua từng tháng: \(0, 1, 1, 2, 3, 5\). Tháng thứ 5 có 5 cặp.

Ràng buộc & Subtasks