Mô tả và yêu cầu

Số fibonacci

Số Fi bonacci đ ượ c xác đ ịnh b ở i công th ức sau:

F0=0

F1=1

Fn=F n-1+F n-2 vớ i n≥2.

Mộ t số ph ầ n tử đầ u ti ên của dãy Fi bonacci : 0,1,1,2,3,5,8,....

Tìm số Fi bonacci th ứ n.

In p u t

Mộ t số nguyên d ươ ng duy nh ất n (n≤1 000 000).

Ou tp u t

Mộ t số nguyên duy nh ấ t l à số Fi bonacci thứ n (kế t quả lấ y ph ầ n dư cho 1 000 000 007).

E x a mp le

I nput:
6

Dữ liệu ra

8

I nput:

20

6765