특별한 기술력
시간 제한1초메모리 제한1024 MB
각 학생을 최대 한 번씩 망치로 쳤을 때 도달할 수 있는 가장 큰 최종 키를 구하고, 그 값을 10^9+7로 나눈 나머지로 출력합니다.
문제
NLCS의 기술력은 세계 제일이다.
기술력이 뛰어난 NLCS Jeju는 키가 커지고 싶은 학생들을 위해 키를 키워 주는 도구 "요술 망치"를 개발했다.
NLCS Jeju는 요술 망치의 임상실험에 참여한 명의 학생에게 요술 망치를 사용하는 실험을 진행했다. 어떤 학생에게 요술 망치를 사용하면 그 학생의 키만큼 다른 모든 학생의 키가 커진다. 다만 요술 망치는 아직 프로토타입 단계라 한 학생에게 최대 한 번만 사용할 수 있다.
NLCS Jeju는 요술 망치의 대단함을 보여 주기 위해, 요술 망치를 사용한 뒤 키가 가장 큰 학생의 키를 최대로 만들고자 한다. 명의 학생에게 요술 망치를 사용해서 만들 수 있는 가장 큰 키를 구해 보자!
입력
첫 번째 줄에 학생의 수 이 주어진다.
두 번째 줄에 각 학생의 키 가 공백으로 구분되어 주어진다.
출력
요술 망치를 적절히 사용해 얻을 수 있는 가장 큰 학생의 키를 출력한다. 키가 매우 커질 수 있으므로, 그 값을 로 나눈 나머지를 출력한다.