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

input:

• Số nguyên dương n (0<n<10$^6$)</li>

output:

• Fn%1000000007

Ví dụ