23827번 - 수열 (Easy)

문제

모든 원소가 양의 정수이고, 길이가 $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$)

힌트