黑暗爆炸OJ

DARKBZOJ

#3745. [Coci2015]Norma

Statistics 下载数据

Description

Input

第1行，一个整数N；

第2~n+1行，每行一个整数表示序列a。

Output

输出答案对10^9取模后的结果。

Sample Input

4
2
4
1
4

Sample Output

109

【数据范围】
N <= 500000
1 <= a_i <= 10^8

Hint

Source

鸣谢 Dzy