#2043. 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

Nguồn: Free Contest 06

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 1 , 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à:

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

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

Dữ liệu vào:

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

Dữ liệu ra:

  • Một dòng duy nhất ghi ra số Fibonacci thứ n (theo modun 10^9+7 ).

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 \#1: 1 ≤ n ≤ 50 ;
  • Subtask \#2: 1 ≤ n ≤ 10^6 ;
  • Subtask \#3: 1 ≤ n ≤ 10^{12} .