409321: GYM103485 C Construction of precious stones

In Ancient Egypt exists precious stones with different values that we can combine many stone with lower value in a stone with high value. The craftman Fábio can make a precious stone with value $$$i$$$ using a precious stone with value $$$i-1$$$, two precious stone with value $$$i-2$$$, and so on, until a precious stone with value $$$1$$$ in which is necessary to have $$$i-1$$$ copies. More precisely, to construct a precious stone $$$i$$$, it is necessary to have $$$i-j$$$ copies of precious stone $$$j$$$ (for every $$$j$$$ between $$$1$$$ and $$$i-1$$$).

A seller of precious stones sells each stone from value $$$1$$$ to $$$n$$$, and the price of precious stone of value $$$i$$$ is $$$a_i$$$.

Find the lowest price to obtain a stone with value $$$k$$$. Note that as $$$n$$$ can be smaller than $$$k$$$, the precious stone with value $$$k$$$ is not necessary selled directly, but it is possible to be constructed from others.

In the first line, we have two integers $$$n$$$ and $$$k$$$, where $$$1 \leq n , k \leq 10^6$$$. The next $$$n$$$ lines we have the prices of the precious stones, the $$$i$$$-th number $$$a_i$$$ is the price of stone with value $$$i$$$, where $$$1 \leq a_i \leq 10^6$$$.

Find the lowest price that we can get a precious stone with value $$$k$$$. As the value can grow too big, print the number modulo $$$10^9+7$$$. Note that we want to minimize the value and print the modulo, and not minimize the modulo.

For a accessible price, it is guaranteed that the chosen value of $$$k$$$ is such that the maximum price is less than $$$10^{18}$$$.

4 4
1 2 10 20

8