Dãy số fibonanci \(f(n)\) được định nghĩa như sau:

• \(f(0)=1\)
• \(f(1)=1\)
• \(f(n)=f(n-1)+f(n-2),\forall n \geq 2\)

Cho số nguyên dương thứ \(n\), hãy tìm số fibonacci thứ \(N (N \leq 1000)\). Vì kết quả có thể rất lớn, hãy lấy kết quả sau khi chia lấy dư cho \(10^9+7\)

Dữ liệu vào

Một dòng duy nhất chứa số nguyên \(N\).

Dữ liệu ra

Một dòng duy nhất chứa số nguyên \(f(n)\)

3

3