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 10^9+7. Help Detective find the answer and tell Kid who is the real artist.
First line of input contains two space separated integers N and K.
Second line of input contains N space separated integers Ai.
Single integer denoting the value of S modulo 10^9+7.
0 < N <= 1e5
0 < K <= 1e15
0 < Ai <= 1e6