32759번 - 준근이와 마법 공방

문제

마법사 준근이는 작은 마법 공방을 운영하고 있다. 준근이네 마법 공방에서는 여러 개의 마력석을 이용해 더 좋은 마력석을 합성해 주는 일을 하고 있다. 어느 날 문득 준근이는 일하기가 귀찮아져 기가 막힌 아이디어를 떠올리게 되는데, 바로 마력석을 자동으로 합성해 주는 기계를 제작하는 것이다!

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

• 준근이가 가지고 있는 마력석들을 모두 기계에 넣는다.
• 기계는 투입된 마력석 중 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 \lt 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円$

힌트