之后小花给了你一个式子

小花希望你能告诉 ta 这个式子在 $\bmod~ (10^9)$ 意义下的值是多少？

Format

Input

第 $1$ 行一个整数 $n$ 表示序列长度。

第 $2$ 行共 $n$ 个整数 $a_i$ 用于描述这个序列的元素。

Output

共 $1$ 行一个整数 $ans$ 表示答案。

Samples

4
2 4 1 4

109

6
8 1 3 9 7 4

1042

输入数据3

见样例文件 ex.in。

输出数据3

见样例文件 ex.out。

Constraints

对于前 $20\%$ 的数据，保证 $1 \le n \le 3000$。

对于前 $40\%$ 的数据，保证 $1 \le n \le 5\times 10^4$。

对于另外 $20\%$ 的数据，保证 $1\le a_i \le 3000$。

对于全部 $100\%$ 的数据，保证 $1 \le n \le 5 \times 10^5$，$1 \le a_i \le 10^9$。