특별한 기술력

NLCS의 기술력은 세계 제일이다.

기술력이 뛰어난 NLCS Jeju는 키가 커지고 싶은 학생들을 위해 키가 커지는 도구 "요술 망치"를 개발하였다.

키가 커지고 싶어 요술 망치의 임상실험에 참여한 $N$명의 학생들에게 요술 망치를 사용하는 실험을 진행하게 되었다. 어떤 학생에게 요술 망치를 사용하면 그 학생의 키만큼 다른 모든 학생의 키가 커진다. 하지만 요술 망치는 아직 프로토타입 단계라 한 학생에게 최대 한 번밖에 사용할 수 없다.

NLCS Jeju는 요술 망치의 대단함을 강조하기 위해 요술 망치를 사용한 후 키가 가장 큰 학생의 키를 최대로 만들고자 한다.

$N$명의 학생에게 요술 망치를 사용해서 만들 수 있는 가장 큰 키를 구해보자!

첫 번째 줄에 학생의 수 $N$이 주어진다.

두 번째 줄에 각 학생의 키 $H_i$가 공백으로 구분되어 주어진다.

요술 망치를 적절히 사용하여 얻을 수 있는 가장 큰 학생의 키를 출력한다. 단, 학생의 키가 너무 커질 수 있기 때문에 이를 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \le N \le 200\,000$
• $1 \le H_i \le 10^9$