Dãy Fibonacci

Trung bình

vòng lặpsố lớn6 test · 3 giây

Dãy Fibonacci định nghĩa: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2).

Cho n, hãy in ra F(n) chia lấy dư cho 1 000 000 007.

Dữ liệu vào

Một dòng chứa số nguyên n (0 ≤ n ≤ 10⁶).

In ra F(n) mod 1 000 000 007.

Input

Output

Input

Output

586268941

F(50) = 12586269025, lấy dư cho 1 000 000 007 được 586268941

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.