Dãy số Fibonacci là một trong những dãy số tự nhiên nổi tiếng nhất, định nghĩa bởi công thức truy hồi: \[F(0) = 0, \quad F(1) = 1\] \[F(N) = F(N-1) + F(N-2) \quad (\text{với } N \ge 2)\]

Nếu triển khai đệ quy thuần túy không có tối ưu, chương trình sẽ gặp trạng thái bùng nổ tổ hợp và chạy cực kỳ chậm khi \(N\) tăng lên. Hãy áp dụng kỹ thuật đệ quy có nhớ (Memoization) hoặc quy hoạch động để giải quyết bài toán với \(N \le 45\).

Định dạng đầu vào

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

Định dạng đầu ra

• Một số nguyên duy nhất là giá trị số Fibonacci thứ \(N\).

Ví dụ

Input:

10

Output:

55

Ràng buộc

• 30% số điểm ứng với \(N \le 15\).
• 70% số điểm còn lại không có ràng buộc gì thêm.