#3745. [Coci2015]Norma

题目描述

输入格式

第1行，一个整数N；

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

输出格式

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

样例

样例输入

4  

2  

4  

1  

4

样例输出

109  

  

【数据范围】  

N <= 500000  

1 <= a_i <= 10^8

数据范围与提示