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 :

FIBGCD

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 :

First line of input contains two space separated integers N and K.
Second line of input contains N space separated integers Ai.

Output :

Single integer denoting the value of S modulo 1000000007.

Constraints :

0 < N <= 100000
0 < K <= 1015
0 < Ai <= 1000000

Example

Input:

5 1
2 4 2 1 4

Output:

12

Added by:Sahil Grover
Date:2017-05-21
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:INSOMNIA 2017

hide comments
2019-10-26 12:22:23
what is the use of K
2019-09-02 16:32:18 Simes
Missing image can be found at https://codevillage.sdslabs.co/problems/INS17M

Edit: And just after I left the comment, the image appeared. I'll leave the comment in case it disappears again.

Last edit: 2019-09-02 16:33:03
2017-12-17 17:31:50
+1 nice problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.