Cho dãy số Fibonacci được xác định như sau: \(F_1=F_2=1, F_n=F_{n-1}+F_{n-2}, \forall n\geq 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

Input: \(n (0<n \leq 10^6)\)

Output: \(F_n \)%1000000007