SP31893 INS17M - Fibonacci and Easy GCD
Description
The Little Detective and the Kid are tired of fighting with each other, so they try to find the winner by a simple problem.
Kid gives the Detective an array **A** of size **N** and challenges him to find the following sum :
Where
**Fib (i)** is the famous Fibonacci sequence such that **Fib (0) =0** , **Fib(1) = 1** and **Fib(i) = Fib(i-1) + Fib(i-2)** for **i>=2**.
**GCD (x,y)** represents the greatest common divisor of **x** and **y**.
Since the answer can be very large, Kid asks Little Detective to find it modulo 1000000007. Help Detective find the answer and tell Kid who is the real artist.
Input Format
N/A
Output Format
N/A