Cho dãy số Fibonacci được xác định như sau: F1=F2=1,Fn=Fn−1+Fn−2,∀n≥3. Một số số hạng ban đầu của dãy như sau: 1,1,2,3,5,8,13,21,34...
Yêu cầu: Tính số Fibonacci thứ n, kết quả có thể rất lớn nên ta phải chia lấy dư cho 1000000007
Dữ liệu: Số nguyên dương n (0<n<106)
Kết quả: Fn%1000000007
input
3
output
2