제목 설명

주어진 $n$개의 양의 정수 $a_1, a_2,..., a_n$, 구 의 값입니다 (답 $mod$ $10^9+7$).

형식 입력

첫 번째 행의 양의 정수 $n$입니다.

다음으로 $n$행, 각 행의 양의 정수, 각각 $a_1, a_2,..., a_n$입니다.

출력 형식

단 한 줄의 답안.

샘플

3
6
10
15

1595

데이터 범위 및 규약

$1\le n\le 10^5,1\le a_i\le 10^7$，총 3조의 데이터.