There are ~n~ people and ~n~ gifts, labelled ~1~ through ~n~. The gifts are handed out according to a uniformly random permutation: every permutation of the ~n~ gifts is equally likely.

Person ~i~ receives value ~w_i~ if they get gift ~i~, and otherwise receives ~0~. Let ~X~ be the total value received by everyone.

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~ integers ~w_1, w_2, \ldots, w_n~.

Output

Print a single integer: the expected total value 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 2 3

Output

2

Explanation

The expected value is ~(1 + 2 + 3)/3 = 2~.

Example 2

Input

1
7

Output

7

Explanation

There is only one permutation, so person ~1~ always receives gift ~1~.

Example 3

Input

2
5 5

Output

5

Explanation

Each person gets their own gift with probability ~1/2~, so the expected total is ~5/2 + 5/2 = 5~.