#412. BIGFIBO - Dãy số Fibonacci

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Dãy số Fibonacci được định nghĩa bởi công thức:

\left\{ \begin{array}{l} {F_0} = {F_1} = 1\\ {F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2 \end{array} \right.

Yêu cầu: Cho số nguyên không âm n , hãy tính F_n .

Dữ liệu vào:

  • Một dòng duy nhất chứa số nguyên không âm n .

Dữ liệu ra:

  • Một dòng duy nhất chứa số nguyên là phần dư của F_n khi chia cho 10^9 + 7 .

Ví dụ:

Dữ liệu vào:
10
Dữ liệu ra:
89
Dữ liệu vào:
45
Dữ liệu ra:
836311896

Giới hạn:

  • 0 ≤ n ≤ 10^{18} .