Migrated from Lutece 1050 Different game

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Alice is playing a new game recently. In this game, there are $n$ different kinds of cards. We assume that Alice have $c_i$ pieces of cards for $i_{th}$ kind.

Alice is asked to divide them into $m$ piles and then arrange each pile in one line. After that, Alice will get $m$ sequences. For convenience, the sequences are labeled $S_1, S_2, \cdots , S_m$. For each $i < j$, Alice will get some points, equal to the length of the LCS(longest common subsequence) of $S_i$ and $S_j$. The total points is the sum of points for all $i < j$.

Now Alice is wondering the maximum points she can get.

As is known to everyone of you, Bob loves Alice very much. Could you tell Bob the answer to help Bob leave a good impression on Alice.

Input

The first line contains $2$ integers $m$ and $n$, indicating the number of sequences and the number of different kinds of card.

The second line contains $n$ integers $c_i$, indicating the number of $i_{th}$ card.

It is guaranteed that $1 \leq n, m \leq 100000, 0 \leq c_i \leq 100000$.

Output

Print the answer module 1000000007 in one line.

Samples

2 2
2 3

2

Resources

The 13th UESTC Programming Contest Final