Tính số Fibonacci lớn

Bối cảnh

Cho một số nguyên \(N\). Chắc bạn đã khá quen thuộc với dãy Fibonacci là gì rồi. Đó là dãy số mà số tiếp theo là tổng của hai số liền trước, ví dụ: \(0, 1, 1, 2, 3, 5, 8, 13,...\) với hai số đầu tiên là \(0\) và \(1\). Cụ thể :

Yêu cầu

\(F_0 = 0; F_1 = 1; F_2 = 1; F_3 = 2; F_4 = 3; F_5 = 5; F_6 = 8;...\)

Hãy ghi ra giá trị của \(F_N\) với vị trí là \(N\).

Input

Một số nguyên \(N\ (1\leq N\leq 5000)\).

Output

Một số nguyên là kết quả của bài.

Ràng buộc

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

Ví dụ 1

Input

7

Output

13

Giải thích ví dụ

Ví dụ 1

7

Giá trị của số Fibonacci tại vị trí 7 là 13, vì các số trước đó là 0, 1, 1, 2, 3, 5, 8.

Thông tin học tập

• Buổi: B21
• Concepts: BigNum using std::string
• Giới hạn kiến thức: B01-B21
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 10