Carol has too many carnivorous plants! She has only one three-foot wide shelf and her plants are growing very quickly (as they are being fed properly), so she needs to sell some. Being very poor, Carol decides to scam her friends so that the more plants they buy, the more the plants will cost. She charges them ~c^x~ dollars per plant, with ~x~ being the number of flowers that person has bought, and ~c~ being the cost of the specific plant. The first plant will be very cheap and cost one dollar, however following plants will quickly increase in price. This may make it difficult for even your computer to store the costs!

Unfortunately, all her friends are computer nerds, and they catch onto her scam! However, they really want carnivorous plants as Carol is a very good collector, so they try to buy plants anyway. The computer nerd tries to scam Carol back, by bringing ~m~ friends (including themselves) to buy plants for the computer nerd. The computer nerd wants ~n~ plants and, because he's a computer nerd, wishes to minimize the cost of the plants.

Input Specification

The first line will contain two space separated integers ~n~ and ~m~.

The second line will contain ~n~ space separated integers, which are the costs of the plants.

Constraints

~1 \le n, m \le 100~

~0 \le c \le 50~

Output Specification

The minimum cost to buy all ~n~ plants, mod ~1\,000\,000\,007~.

Sample Input

4 2
1 2 3 4

Sample Output

5

Explanation

One person can buy the ~$4~ plant for ~$1~ ~(4^0)~ and the ~$1~ plant for ~$1~ ~(1^1)~. The second person will buy the ~$3~ plant for ~$1~ ~(3^0)~ and the ~$2~ plant for ~$2~ ~(2^1)~. Our total cost is ~1 + 1 + 1 + 2 = 5~.