E. A Random Traveller
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hey, I'm sure that you love to travel a lot. Now, you have $$$n$$$ cities left in your wish list, $$$i$$$-th of which costs $$$a_i$$$ to visit, and obviously, you want to visit all of them. To do so, you will follow the following steps:

  1. Choose a random city, numbered $$$i$$$ uniformly in the range from $$$1$$$ to $$$n$$$ and visit city $$$i$$$.
  2. In case you have successfully visited all cities, stop your journey.
  3. Otherwise, go to step $$$1$$$.

Note that, you may visit one city more than once. Find the expected total cost you need to visit all the $$$n$$$ cities. It can be shown that it can be represented as $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers and $$$q \ne 0 \bmod{10^9+7}$$$. Print the value of $$$p \cdot q^{-1} \bmod{10^9+7}$$$.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of cities.

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — $$$i$$$-th of which represents the costs of visiting city $$$i$$$ i.e. $$$a_i$$$ $$$(1 \le a_i \le 10^5)$$$.

Output

Print a single integer — the expected total cost to visit all the cities written as $$$p \cdot q^{-1} \bmod{10^9+7}$$$.

Examples
Input
3
1 2 3
Output
11
Input
1
5
Output
5