Số Fibonacci thứ N

Dãy Fibonacci được định nghĩa như sau:

• \(F_1 = F_2 = 1\),
• \(F_n = F_{n-1} + F_{n-2}\) với mọi \(n \ge 3\).

Cho số nguyên \(N\), hãy tính \(F_N\). Do giá trị này có thể rất lớn, hãy in ra phần dư của \(F_N\) khi chia cho \(10^9 + 7\).

Input

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

Output

• In ra một số nguyên: \(F_N \bmod (10^9+7)\).

Constraints

• \(1 \le N \le 10^6\)

Sample Input 1

5

Sample Output 1

5

Sample Input 2

1

Sample Output 2

1

Sample Input 3

12

Sample Output 3

144