시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB121639331132.062%

문제

모든 원소가 양의 정수이고, 길이가 $N$인 수열 $A_1, A_2, ..., A_N$이 주어진다. $1 \le i < j \le N$을 만족하는 모든 정수쌍 $(i, j)$에 대해 $A_i \times A_j$의 합을 $1\, 000 \, 000 \, 007$로 나눈 나머지를 구하시오.

입력

첫째 줄에 수열 $A$의 길이 $N$이 주어진다.

둘째 줄에 수열 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

출력

$1 \le i < j \le N$을 만족하는 모든 정수쌍 $(i, j)$에 대해 $A_i \times A_j$의 합을 $1\, 000 \, 000 \, 007$로 나눈 나머지를 출력하여라.

제한

  • $2 \le N \le 500\,000$
  • $1 \le A_i \le 500\, 000$ ($1 \le i \le N$)

예제 입력 1

3
1 2 3

예제 출력 1

11

$1 \times 2 + 2 \times 3 + 1 \times 3 = 11 $

 

출처

High School > 세종과학예술영재학교 > SASA Programming Contest 2021 C1번