You are given an array $a_1,\ a_2,\ ...,\ a_n$ of size $N$ and the following expression:

Find the value of the provided expression modulus $1000000007$.

Input format

• The first line contains an integer $N$ denoting the number of elements in array $a$.
• The second line contains $N$ space-separated integers denoting the elements of $a$.

Output format

Find the value of the above expression modulus $1000000007$.

Constraints
$2 ≤ N ≤ 10^5\\ 1 ≤ a[i] ≤ 10^6$