Consecutive Neighbours

A uniformly random permutation $\pi$ of $1, 2, \ldots, n$ is generated. For each $i = 1, 2, \ldots, n - 1$, if the values $i$ and $i + 1$ appear in adjacent positions of $\pi$, you score $w_i$.

Let $X$ be the total score. Output the expected value of $X$.

It can be shown that the answer can be expressed as a rational number $P/Q$ in lowest terms with $Q$ coprime to $10^9 + 7$. Output $P \cdot Q^{-1} \bmod (10^9 + 7)$.

Input

The first line contains an integer $n$.

The second line contains $n - 1$ integers $w_1, w_2, \ldots, w_{n-1}$. If $n = 1$, this line is empty.

Output

Print a single integer: the expected total score modulo $10^9 + 7$.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $0 \le w_i \le 10^9$

Example 1

3
1 1

333333337

Explanation

There are two pairs, $(1, 2)$ and $(2, 3)$. Each pair of consecutive values occupies adjacent positions with probability $2/3$, so the expected score is $4/3$. $4 \cdot 3^{-1} \equiv 333333337 \pmod{10^9 + 7}$.

Example 2

2
10

10

Explanation

The two values are always adjacent, so the score is always $10$.

Example 3

1

0

Explanation

There are no consecutive pairs when $n = 1$.