INS17M  Fibonacci and Easy GCD
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(i1) + Fib(i2) 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 :
First line of input contains two space separated integers N and K.
Second line of input contains N space separated integers A_{i}.
Output :
Single integer denoting the value of S modulo 1000000007.
Constraints :
0 < N <= 100000
0 < K <= 10^{15}
0 < A_{i} <= 1000000
Example
Input:
5 1 2 4 2 1 4
Output:
12
hide comments
barishnamazov:
20171217 17:31:50
+1 nice problem


utkarsha gaumat:
20170616 21:28:54
Last edit: 20170616 21:31:46 
Added by:  Sahil Grover 
Date:  20170521 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  INSOMNIA 2017 