문제
NLCS의 기술력은 세계 제일이다.
기술력이 뛰어난 NLCS Jeju는 키가 커지고 싶은 학생들을 위해 키가 커지는 도구 "요술 망치"를 개발하였다.
키가 커지고 싶어 요술 망치의 임상실험에 참여한 $N$명의 학생들에게 요술 망치를 사용하는 실험을 진행하게 되었다. 어떤 학생에게 요술 망치를 사용하면 그 학생의 키만큼 다른 모든 학생의 키가 커진다. 하지만 요술 망치는 아직 프로토타입 단계라 한 학생에게 최대 한 번밖에 사용할 수 없다.
NLCS Jeju는 요술 망치의 대단함을 강조하기 위해 요술 망치를 사용한 후 키가 가장 큰 학생의 키를 최대로 만들고자 한다.
$N$명의 학생에게 요술 망치를 사용해서 만들 수 있는 가장 큰 키를 구해보자!
출력
요술 망치를 적절히 사용하여 얻을 수 있는 가장 큰 학생의 키를 출력한다. 단, 학생의 키가 너무 커질 수 있기 때문에 이를 10ドル^9+7$로 나눈 나머지를 출력한다.
제한
- 1ドル \le N \le 200,000円$
- 1ドル \le H_i \le 10^9$
W3sicHJvYmxlbV9pZCI6IjMxNjc0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI5XHViY2M0XHVkNTVjIFx1YWUzMFx1YzIyMFx1YjgyNSIsImRlc2NyaXB0aW9uIjoiPHA+TkxDU1x1Yzc1OCBcdWFlMzBcdWMyMjBcdWI4MjVcdWM3NDAgXHVjMTM4XHVhY2M0IFx1YzgxY1x1Yzc3Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTMwXHVjMjIwXHViODI1XHVjNzc0IFx1YjZmMFx1YzViNFx1YjA5YyBOTENTIEplanVcdWIyOTQgXHVkMGE0XHVhYzAwIFx1Y2VlNFx1YzljMFx1YWNlMCBcdWMyZjZcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWQwYTRcdWFjMDAgXHVjZWU0XHVjOWMwXHViMjk0IFx1YjNjNFx1YWQ2YyAmcXVvdDtcdWM2OTRcdWMyMjAgXHViOWRkXHVjZTU4JnF1b3Q7XHViOTdjIFx1YWMxY1x1YmMxY1x1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGE0XHVhYzAwIFx1Y2VlNFx1YzljMFx1YWNlMCBcdWMyZjZcdWM1YjQgXHVjNjk0XHVjMjIwIFx1YjlkZFx1Y2U1OFx1Yzc1OCBcdWM3ODRcdWMwYzFcdWMyZTRcdWQ1ZDhcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTVjICROJFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNjk0XHVjMjIwIFx1YjlkZFx1Y2U1OFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGMgXHVjNjk0XHVjMjIwIFx1YjlkZFx1Y2U1OFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgXHVhZGY4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWQwYTRcdWI5Y2NcdWQwN2MgXHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVkMGE0XHVhYzAwIFx1Y2VlNFx1YzljNFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YzY5NFx1YzIyMCBcdWI5ZGRcdWNlNThcdWIyOTQgXHVjNTQ0XHVjOWMxIFx1ZDUwNFx1Yjg1Y1x1ZDFhMFx1ZDBjMFx1Yzc4NSBcdWIyZThcdWFjYzRcdWI3N2MgXHVkNTVjIFx1ZDU1OVx1YzBkZFx1YzVkMFx1YWM4YyBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YmM4OFx1YmMxNlx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+TkxDUyBKZWp1XHViMjk0IFx1YzY5NFx1YzIyMCBcdWI5ZGRcdWNlNThcdWM3NTggXHViMzAwXHViMmU4XHVkNTY4XHVjNzQ0IFx1YWMxNVx1Yzg3MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjk0XHVjMjIwIFx1YjlkZFx1Y2U1OFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVkNmM0IFx1ZDBhNFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjZDVjXHViMzAwXHViODVjIFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiROJFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGMgXHVjNjk0XHVjMjIwIFx1YjlkZFx1Y2U1OFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQwYTRcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVkNTU5XHVjMGRkXHVjNzU4IFx1ZDBhNCAkSF9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2OTRcdWMyMjAgXHViOWRkXHVjZTU4XHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVkMGE0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVkMGE0XHVhYzAwIFx1YjEwOFx1YmIzNCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzc0XHViOTdjICQxMF45KzckXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAyMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgSF9pIFxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxNjc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXhjZXB0aW9uYWwgVGVjaG5vbG9neSIsImRlc2NyaXB0aW9uIjoiPHA+TkxDUyBKZWp1JiMzOTtzIHRlY2hub2xvZ3kgaXMgdGhlIGJlc3QgaW4gdGhlIHdvcmxkLjxcL3A+XHJcblxyXG48cD5Gb3Igc3R1ZGVudHMgd2hvIHdhbnQgdG8gZ3JvdyB0YWxsZXIsIE5MQ1MgSmVqdSBoYXMgZGV2ZWxvcGVkIHRoZSAmcXVvdDtNaXJhY2xlIE1hbGxldCZxdW90Oywgd2hpY2ggaXMgYSB0b29sIHRoYXQgY2FuIGNoYW5nZSBhIHBlcnNvbiYjMzk7cyBoZWlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5MQ1MgSmVqdSBjb25kdWN0ZWQgYSBjbGluaWNhbCB0cmlhbCBhZ2FpbnN0ICROJCBzdHVkZW50cyB3aG8gYXJlIHdpbGxpbmcgdG8gZ2V0IHRhbGxlci4gSWYgdGhlIG1hbGxldCBpcyB1c2VkIGFnYWluc3QgYSBjZXJ0YWluIHN0dWRlbnQsIHRoZSBoZWlnaHQgb2Ygb3RoZXIgc3R1ZGVudHMgd2lsbCBiZSBpbmNyZWFzZWQgYnkgaGlzIGhlaWdodC4gSG93ZXZlciwgYmVjYXVzZSB0aGUgTWlyYWNsZSBNYWxsZXQgaXMgc3RpbGwgaW4gdGhlIHByb3RvdHlwZSBzdGFnZSwgZWFjaCBzdHVkZW50IGNhbiBvbmx5IHVzZSBpdCBhdCBtb3N0IG9uY2UuPFwvcD5cclxuXHJcbjxwPk5MQ1MgSmVqdSB3YW50cyB0byBlbXBoYXNpemUgdGhlIGdyZWF0bmVzcyBvZiB0aGUgbWlyYWNsZSBtYWxsZXQmbmJzcDtieSB1c2luZyBpdCB0byBtYXhpbWl6ZSB0aGUgaGVpZ2h0IG9mIHRoZSB0YWxsZXN0IHN0dWRlbnQgYWZ0ZXIgaXRzIHVzZS48XC9wPlxyXG5cclxuPHA+SGVscCBOTENTIEplanUgdG8gZmluZCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBoZWlnaHQgYWZ0ZXIgdXNpbmcgdGhlIG1hbGxldCB0byAkTiQgc3R1ZGVudHMhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyJm5ic3A7JE4kICQtJCB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJE4kIGludGVnZXJzJm5ic3A7JEhfaSQmbmJzcDskLSQgdGhlICRpJC10aCBzdHVkZW50JiMzOTtzIGhlaWdodC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaW5kIG91dCZuYnNwO3RoZSBtYXhpbXVtIHBvc3NpYmxlIGhlaWdodCBvZiB0aGUgdGFsbGVzdCBzdHVkZW50IGFmdGVyIGFwcHJvcHJpYXRlbHkgdXNpbmcgdGhlIE1pcmFjbGUgTWFsbGV0LiBIb3dldmVyLCBzaW5jZSB0aGUgc3R1ZGVudCYjMzk7cyBoZWlnaHQgbWF5IGJlIHRvbyB0YWxsLCBwcmludCBhIHNpbmdsZSBpbnRlZ2VyICQtJCB0aGUgcmVtYWluZGVyIG9mIHRoZSBoZWlnaHQgd2hlbiZuYnNwO2RpdmlkZWQgYnkgJDEwXjkrNyQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAyMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgSF9pIFxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==