Expected Fixed Points

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

3
1 2 3

2

Explanation

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

Example 2

1
7

7

Explanation

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

Example 3

2
5 5

5

Explanation

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