Given an integer NNN, compute the NNN-th Fibonacci number F(N)F(N)F(N) where F(0)=0F(0) = 0F(0)=0, F(1)=1F(1) = 1F(1)=1, and F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2) for n≥2n \ge 2n≥2.
Since the answer may be very large, output it modulo 109+710^9 + 7109+7.
A single integer NNN.
A single integer — F(N)mod (109+7)F(N) \mod (10^9 + 7)F(N)mod(109+7).
0≤N≤1060 \le N \le 10^60≤N≤106
5
F(5)=F(4)+F(3)=3+2=5F(5) = F(4) + F(3) = 3 + 2 = 5F(5)=F(4)+F(3)=3+2=5
10
55