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
dollars per plant, with
being the number of flowers that person has bought, and
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
friends (including themselves) to buy plants for the computer nerd. The computer nerd wants
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
and
.
The second line will contain
space separated integers, which are the costs of the plants.
Constraints


Output Specification
The minimum cost to buy all
plants, mod
.
Sample Input
Copy
4 2
1 2 3 4
Sample Output
Copy
5
Explanation
One person can buy the
plant for
and the
plant for
. The second person will buy the
plant for
and the
plant for
. Our total cost is
.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.
Comments