시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 194 121 86 74.138%

문제

윤이는 Uni-COM에서 컴퓨터 부품을 판매하고 있다. 윤이는 다양한 성능의 CPU를 취급하는데, 손님들이 CPU의 성능을 손쉽게 비교할 수 있도록 벤치마크 표를 만들려고 한다.

모든 CPU 쌍을 직접 비교하는 일은 번거로우므로, 윤이는 CPU를 성능이 낮은 것부터 높은 것까지 정렬한 뒤 이웃한 CPU의 성능이 몇 배 차이가 나는지 측정했다. 그러면 다른 CPU 쌍의 성능 차이도 쉽게 계산할 수 있기 때문이다. 예컨대 CPU $X, Y, Z$에 대해 $X$가 $Y$보다 $a$배 빠르고 $Y$가 $Z$보다 $b$배 빠르다면 $X$는 $Z$보다 $ab$배 빠르다는 사실을 알 수 있다.

윤이는 측정한 자료를 통해 모든 CPU 쌍의 성능 차이를 계산해서 벤치마크 표에 적었다. 구체적으로는, $1\le i<j\le N$을 만족하는 모든 순서쌍 $(i, j)$에 대해 $j$번째 CPU가 $i$번째 CPU보다 몇 배 빠른지를 표에 적었다. 윤이가 표에 적은 수를 전부 더한 값을 계산하시오. 단, 계산 결과가 커질 수 있으므로 $10^9+7$으로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 CPU의 개수 $N$이 주어진다.

두 번째 줄에 $N-1$개의 양의 정수 $m_i$가 공백으로 구분되어 주어진다. $i+1$번째 CPU의 성능이 $i$번째 CPU의 성능의 $m_i$배임을 의미한다.

출력

윤이가 벤치마크 표에 적은 수의 합을 $10^9+7$으로 나눈 나머지를 출력한다.

제한

  • $2 \le N \le 500,000$
  • $1 \le m_i < 10^9$

서브태스크 1 (30점)

$N \le 5,000$

서브태스크 2 (90점)

추가적인 제약 조건이 없다.

예제 입력 1

4
1 2 3

예제 출력 1

20

이 경우 벤치마크 표는 다음과 같다. (단, 답을 계산할 때 CPU의 번호는 제외하고 더해야 한다.)

image of benchmark table

예제 입력 2

4
2 2 4

예제 출력 2

36

예제 입력 3

5
973408385 513124519 802361288 816371495

예제 출력 3

157603704
W3sicHJvYmxlbV9pZCI6IjIwMzEyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQ1BVIFx1YmNhNFx1Y2U1OFx1YjljOFx1ZDBiOSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzI0XHVjNzc0XHViMjk0IFVuaS1DT01cdWM1ZDBcdWMxMWMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YmQ4MFx1ZDQ4OFx1Yzc0NCBcdWQzMTBcdWI5ZTRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3MjRcdWM3NzRcdWIyOTQgXHViMmU0XHVjNTkxXHVkNTVjIFx1YzEzMVx1YjJhNVx1Yzc1OCBDUFVcdWI5N2MgXHVjZGU4XHVhZTA5XHVkNTU4XHViMjk0XHViMzcwLCBcdWMxOTBcdWIyZDhcdWI0ZTRcdWM3NzQgQ1BVXHVjNzU4IFx1YzEzMVx1YjJhNVx1Yzc0NCBcdWMxOTBcdWMyN2RcdWFjOGMgXHViZTQ0XHVhZDUwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViY2E0XHVjZTU4XHViOWM4XHVkMDZjIFx1ZDQ1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgQ1BVIFx1YzMwZFx1Yzc0NCBcdWM5YzFcdWM4MTEgXHViZTQ0XHVhZDUwXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWJjODhcdWFjNzBcdWI4NWNcdWM2YjBcdWJiYzBcdWI4NWMsIFx1YzcyNFx1Yzc3NFx1YjI5NCBDUFVcdWI5N2MgXHVjMTMxXHViMmE1XHVjNzc0IFx1YjBhZVx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAgXHViMTkyXHVjNzQwIFx1YWM4M1x1YWU0Y1x1YzljMCBcdWM4MTVcdWI4MmNcdWQ1NWMgXHViNGE0IFx1Yzc3NFx1YzZjM1x1ZDU1YyBDUFVcdWM3NTggXHVjMTMxXHViMmE1XHVjNzc0IFx1YmE4NyBcdWJjMzAgXHVjYzI4XHVjNzc0XHVhYzAwIFx1YjA5OFx1YjI5NFx1YzljMCBcdWNlMjFcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWIyZTRcdWI5NzggQ1BVIFx1YzMwZFx1Yzc1OCBcdWMxMzFcdWIyYTUgXHVjYzI4XHVjNzc0XHViM2M0IFx1YzI3ZFx1YWM4YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Y2VlOFx1YjMwMCBDUFUgJFgsIFksIFokXHVjNWQwIFx1YjMwMFx1ZDU3NCAkWCRcdWFjMDAgJFkkXHViY2Y0XHViMmU0ICRhJFx1YmMzMCBcdWJlNjBcdWI5NzRcdWFjZTAgJFkkXHVhYzAwICRaJFx1YmNmNFx1YjJlNCAkYiRcdWJjMzAgXHViZTYwXHViOTc0XHViMmU0XHViYTc0ICRYJFx1YjI5NCAkWiRcdWJjZjRcdWIyZTQgJGFiJFx1YmMzMCBcdWJlNjBcdWI5NzRcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjRcdWM3NzRcdWIyOTQgXHVjZTIxXHVjODE1XHVkNTVjIFx1Yzc5MFx1YjhjY1x1Yjk3YyBcdWQxYjVcdWQ1NzQgXHViYWE4XHViNGUwIENQVSBcdWMzMGRcdWM3NTggXHVjMTMxXHViMmE1IFx1Y2MyOFx1Yzc3NFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWMxMWMgXHViY2E0XHVjZTU4XHViOWM4XHVkMDZjIFx1ZDQ1Y1x1YzVkMCBcdWM4MDFcdWM1YzhcdWIyZTQuIFx1YWQ2Y1x1Y2NiNFx1YzgwMVx1YzczY1x1Yjg1Y1x1YjI5NCwgJDFcXGxlIGkmbHQ7alxcbGUgTiRcdWM3NDQmbmJzcDtcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxY1x1YzExY1x1YzMwZCAkKGksIGopJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJGokXHViYzg4XHVjOWY4IENQVVx1YWMwMCAkaSRcdWJjODhcdWM5ZjggQ1BVXHViY2Y0XHViMmU0IFx1YmE4NyBcdWJjMzAgXHViZTYwXHViOTc4XHVjOWMwXHViOTdjIFx1ZDQ1Y1x1YzVkMCBcdWM4MDFcdWM1YzhcdWIyZTQuIFx1YzcyNFx1Yzc3NFx1YWMwMCBcdWQ0NWNcdWM1ZDAgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWM4MDRcdWJkODAgXHViMzU0XHVkNTVjIFx1YWMxMlx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjJlOCwgXHVhY2M0XHVjMGIwIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyAkMTBeOSs3JFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIENQVVx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4tMSRcdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCZuYnNwOyRtX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkaSsxJFx1YmM4OFx1YzlmOCBDUFVcdWM3NTggXHVjMTMxXHViMmE1XHVjNzc0Jm5ic3A7JGkkXHViYzg4XHVjOWY4IENQVVx1Yzc1OCBcdWMxMzFcdWIyYTVcdWM3NTgmbmJzcDskbV9pJFx1YmMzMFx1Yzc4NFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzI0XHVjNzc0XHVhYzAwIFx1YmNhNFx1Y2U1OFx1YjljOFx1ZDA2YyBcdWQ0NWNcdWM1ZDAgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgJDEwXjkrNyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyIFxcbGUgTiBcXGxlIDUwMCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgbV9pICZsdDsmbmJzcDsxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDUsMDAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWM3NzQgXHVhY2JkXHVjNmIwJm5ic3A7XHViY2E0XHVjZTU4XHViOWM4XHVkMDZjIFx1ZDQ1Y1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiAoXHViMmU4LCBcdWIyZjVcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YjU0YyZuYnNwO0NQVVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwJm5ic3A7XHViMzU0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4pPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiaW1hZ2Ugb2YgYmVuY2htYXJrIHRhYmxlXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNmY2YjEwYmMtNzAwOS00ZjgwLWJhNWUtMTI0OGU4YTNkNTE5XC9cIiBzdHlsZT1cIm1heC13aWR0aDogMTAwJTsgd2lkdGg6IDM3OHB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjIwMzEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ1BVIEJlbmNobWFyayIsImRlc2NyaXB0aW9uIjoiPHA+WXVuZWUgaXMgc2VsbGluZyBjb21wdXRlciBjb21wb25lbnRzIGF0IFVuaS1DT00uIFl1bmVlIHNlbGxzIENQVXMgb2YgdmFyaW91cyBwZXJmb3JtYW5jZSZuYnNwO2FuZCBpcyBwbGFubmluZyB0byBtYWtlIGEgYmVuY2htYXJrIHRhYmxlIHNvIHRoYXQgY3VzdG9tZXJzIGNhbiBlYXNpbHkgY29tcGFyZSB0d28gQ1BVcy48XC9wPlxyXG5cclxuPHA+U2luY2UgaXQmIzM5O3MgdGVkaW91cyB0byBjb21wYXJlIGV2ZXJ5IHBhaXIgb2YgQ1BVcywmbmJzcDtZdW5lZSBzb3J0ZWQgdGhlIENQVXMgaW4gaW5jcmVhc2luZyBvcmRlciBvZiBwZXJmb3JtYW5jZSBhbmQgbWVhc3VyZWQgdGhlIHJhdGlvIG9mIHBlcmZvcm1hbmNlJm5ic3A7b2YgZWFjaCBhZGphY2VudCBwYWlyIG9mIENQVXMuIFRoZW4gWXVuZWUmbmJzcDtjYW4gZWFzaWx5IGRldGVybWluZSB0aGUgcmF0aW8gb2YgcGVyZm9ybWFuY2UmbmJzcDtmb3IgYW55IHBhaXIgb2YgQ1BVcy4gRm9yIGV4YW1wbGUsIGlmIENQVSAkWCQgaXMgJGEkIHRpbWVzIGZhc3RlciB0aGFuIENQVSAkWSQmbmJzcDthbmQgJFkkIGlzICRiJCB0aW1lcyBmYXN0ZXIgdGhhbiBDUFUgJFokLCB0aGVuICRYJCBpcyAkYWIkIHRpbWVzIGZhc3RlciB0aGFuICRaJC48XC9wPlxyXG5cclxuPHA+VXNpbmcgdGhlc2UgbWVhc3VyZW1lbnRzLCBZdW5lZSBjb21wdXRlZCBhbGwgdGhlIHJhdGlvcyBvZiBwZXJmb3JtYW5jZSZuYnNwO2ZvciBhbGwgcGFpcnMgb2YgQ1BVcy4gU3BlY2lmaWNhbGx5LCBmb3IgZWFjaCAkKGksIGopJCBzdWNoIHRoYXQmbmJzcDskMVxcbGUgaSZsdDtqXFxsZSBOJCwgWXVuZWUgd3JvdGUgZG93biBob3cgbWFueSB0aW1lcyBDUFUgJGokIGlzIGZhc3RlciB0aGFuIENQVSAkaSQuIENvbXB1dGUgdGhlIHN1bSBvZiBhbGwgbnVtYmVycyBZdW5lZSB3cm90ZSBkb3duLiBTaW5jZSB0aGlzIHN1bSBjYW4gYmUgbGFyZ2UsIG91dHB1dCBpdCBtb2R1bG8gJDEwXjkrNyQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSwgdGhlIG51bWJlciBvZiBDUFVzICROJCBpcyBnaXZlbi48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHNlY29uZCBsaW5lLCAkTi0xJCBwb3NpdGl2ZSBpbnRlZ2VycyAkbV9pJCBhcmUgZ2l2ZW4sIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuIEl0IG1lYW5zIENQVSAkaSsxJCBpcyAkbV9pJCB0aW1lcyBmYXN0ZXIgdGhhbiBDUFUgJGkkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc3VtIG9mIHRoZSBudW1iZXJzIFl1bmVlIHdyb3RlIGRvd24gaW4gdGhlIGJlbmNobWFyayB0YWJsZSwgbW9kdWxvICQxMF45KzckLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZSBOIFxcbGUgNTAwLDAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZSBtX2kgJmx0OyZuYnNwOzEwXjkkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNSwwMDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5JbiB0aGlzIGV4YW1wbGUsIHRoZSBiZW5jaG1hcmsgdGFibGUgaXMgYXMgZm9sbG93cy4gKE5vdGUgdGhhdCZuYnNwO3lvdSBzaG91bGQgbm90IGFkZCB1cCB0aGUgQ1BVIG51bWJlcnMuKTxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cImltYWdlIG9mIGJlbmNobWFyayB0YWJsZVwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzZmNmIxMGJjLTcwMDktNGY4MC1iYTVlLTEyNDhlOGEzZDUxOVwvXCIgc3R5bGU9XCJoZWlnaHQ6IDM3NnB4OyB3aWR0aDogMzc4cHg7XCIgXC8+PFwvcD5cclxuIn1d

채점 및 기타 정보

  • 예제는 채점하지 않는다.