Số Fibonacci 1.

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Dãy số Fibonacci được định nghĩa như sau: F1 = 0, F2 = 1; Fi = Fi-1 + Fi-2. Hãy viết chương trình in ra số Fibonacci thứ n.

Input

Số nguyên dương n.(1≤n≤93)

Output

Số fibonacci thứ n.

Ràng buộc

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

Ví dụ 1

Input

5

Output

3

Thông tin học tập

• Buổi: B07
• Concepts: functions, foundational number theory, divisors, primality, gcd, digits, Fibonacci
• Giới hạn kiến thức: B01-B07
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10