CSES - Fibonacci Numbers | Số Fibonacci

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
kitsune , Elektrikar
Dạng bài
Điểm: 1500 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Các số Fibonacci có thể được định nghĩa như sau:

  • \(F_0 = 0\)
  • \(F_1 = 1\)
  • \(F_n = F_{n−2} + F_{n−1}\)

Nhiệm vụ của bạn là tính giá trị của \(F_n\) với \(n\) được cho.

Input

  • Dòng đầu vào duy nhất có một số nguyên \(n\).

Output

  • In giá trị của \(F_n\) chia lấy dư cho \(10^9 + 7\).

Constraints

  • \(0 \le n \le 10^{18}\)

Example

Sample input

10

Sample output

55

Bình luận