Wizard Junkeun and the Magic Workshop

Junkeun is a wizard who runs a small magic workshop. At his workshop, he combines several mana stones into better ones. One day he gets tired of the work and decides to build a machine that merges mana stones automatically.

The machine merges mana stones as follows.

• Junkeun puts all of his mana stones into the machine.
• The machine selects $2$ of the stones it received.
• It combines the two selected stones into a new mana stone. The mana value of the new stone is the sum of the mana values of the two ingredients. The ingredients are not consumed.
  • When it creates a new stone, it always creates the one with the largest mana value among the new stones it can make.
  • A stone created this way can be used as an ingredient later.
• It returns all stones that were not used, all stones that were used, and the new stone as the result. Junkeun takes the result back.

Before starting the machine, Junkeun wants to know the mana value of the last stone created after repeating this process $N$ times. Given $M$ stones with mana values $a_1$, $a_2$, $a_3$, $\cdots$, $a_M$ placed into the machine at the start, write a program that finds the mana value of the last stone created.

The first line contains $N$ and $M$, separated by a space.

The second line contains the integers $a_1$, $a_2$, $a_3$, $\cdots$, $a_M$, separated by spaces.

Print the mana value of the last stone created. The absolute value can be very large, so express the value as $p \times q + r$ using three integers $p$, $q$, and $r$, and print $r$ instead. ($0 \le r < p = 10^9+7$)

• $1 \le N \le 1\,000\,000$
• $2 \le M \le 100\,000$
• $-100\,000 \le a_i \le 100\,000$