Title Description

Given $n$positive integers $a_1,$a_2,..., $a_n$, find the value of it.(Answer $mod$ $10 ^ 9+7$)

Input format

The first line is a positive integer $n$.

Next $n$ lines, each line contains a positive integer, namely $a_1,$a_2,..., $a_n$.

Output format

Only one line of answer.

Example

3
6
10
15

1595

Data scope and agreement

$1\le n\le 10^5,1\le a_i\le 10^7$， There are a total of 3 sets of data.