#2043. SỐ FIBONACCI

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử và , các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là:

Nhập vào số nguyên dương . Tính số Fibonacci thứ . In ra phần dư của kết quả khi chia cho .

Dữ liệu vào:

• Một dòng duy nhất chứa số nguyên dương .

Dữ liệu ra:

• Một dòng duy nhất ghi ra số Fibonacci thứ (theo modun ).

Ví dụ:

Dữ liệu vào:

10

Dữ liệu ra:

55

Dữ liệu vào:

50

Dữ liệu ra:

586268941

Giới hạn:

• Subtask ;
• Subtask ;
• Subtask .