## 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(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 **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

Added by: | kryptox |

Date: | 2017-05-21 |

Time limit: | 2s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | INSOMNIA 2017 |