Mr. C has had a change of heart from being a lonely developer to finally getting a girlfriend, Ms. C (they are not related by blood). As the courteous fellow he is, he has decided to buy some flowers for her.
Ms. C wants 
~N~ flowers with flower 
~i~ costing 
~c_i~, a positive integer. The store, Carol's Flowers, has 
~F~ flowers, where 
~F \ge N~. Each flower can only be bought once, and since Mr. C lives in a computer science problem, the cost of the flowers are exponential. In other words, the second flower he buys is the price of the flower squared, and the third flower he buys is the price of the flower cubed, and so on.
Mr. C is poor, but he needs to satisfy Ms. C. Can you find out the minimum value Mr. C has to pay for ~N~ flowers?
Input Specification
The first line of input contains 
~2~ integers, ~F~ and ~N~ 
~(1 \le N \le F \le 1000)~.
The next ~F~ lines contain 
~1~ integer each. The 
~i^\text{th}~ line contains the positive integer ~c_i~ 
~(1 \le c_i \le 1000)~.
- For 5 of the 15 available marks,
~N \le 10~ and 
~c_i \le 10~.
- For an additional 5 of the 15 available marks,
~N \le 100~ and 
~c_i \le 100~.
Output Specification
A single integer representing the minimum price Mr. C has to pay for ~N~ flowers mod 
~1\,000\,000\,007~ 
~(= 10^9+7)~.
Sample Input
7 3
2
5
2
9
100
56
3
Sample Output
15
Explanation for Sample Output
The cheapest way to buy 
~3~ flowers is to buy the last flower, the third flower, and the first flower. That is, 
~3^1+2^2+2^3 = 15~ is the minimum price.
Comments
Where would we input i?
sad to find that nobody replied to your comment in 1 whole year.