준근이와 마법 공방

마법사 준근이는 작은 마법 공방을 운영한다. 준근이의 공방에서는 여러 개의 마력석을 합성해 더 좋은 마력석을 만드는 일을 한다. 어느 날 준근이는 일이 귀찮아져서 마력석을 자동으로 합성하는 기계를 만들기로 한다.

기계의 마력석 합성 과정은 다음과 같다.

• 준근이가 가지고 있는 마력석을 모두 기계에 넣는다.
• 기계는 투입된 마력석 중 $2$개를 선택한다.
• 선택한 두 마력석을 합쳐 새로운 마력석을 만든다. 새 마력석의 마나 수치는 재료로 쓴 두 마력석의 마나 수치의 합이다. 재료로 쓴 마력석은 사라지지 않는다.
  • 새 마력석을 만들 때는 항상 만들 수 있는 새 마력석 중 마나 수치가 가장 큰 마력석을 만든다.
  • 이 과정으로 만들어진 새 마력석도 이후에 재료로 쓸 수 있다.
• 재료로 쓰지 않은 마력석, 재료로 쓴 마력석, 새 마력석을 결과물로 반환한다. 준근이는 이 결과물을 다시 가져간다.

준근이는 기계를 가동하기 전에 위 과정을 $N$번 반복했을 때 마지막에 만들어질 마력석의 마나 수치를 알고 싶어 한다. 처음에 마나 수치가 $a_1$, $a_2$, $a_3$, $\cdots$, $a_M$인 마력석 $M$개를 기계에 넣었을 때 마지막에 만들어질 마력석의 마나 수치를 구하는 프로그램을 만들어 보자.

첫 번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 정수 $a_1$, $a_2$, $a_3$, $\cdots$, $a_M$이 공백으로 구분되어 주어진다.

첫 번째 줄에 마지막으로 만들어질 마력석의 마나 수치를 출력한다. 수치의 절댓값이 매우 클 수 있으므로, 수치를 세 정수 $p$, $q$, $r$을 사용한 식 $p \times q + r$로 나타낼 때 $r$을 대신 출력한다. ($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$