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

Input

3
1 1

Output

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

Input

2
10

Output

10

Explanation

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

Example 3

Input

1

Output

0

Explanation

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