Stacking Pizzas

Time limit1sMemory limit1024 MB

Summary

Given a_i pizzas of each size i, sum over all stacking orders the number of pizzas visible from above, modulo 1000000007.

Level: Medium6 of 10
Topics: Combinatorics, Probability, Math
Solved: No attempts yet

Problem

There are $a_1$ pizzas of size $1$ , $a_2$ pizzas of size $2$ , $\cdots$ , and $a_N$ pizzas of size $N$ . You want to stack all of these pizzas so that their centers coincide.

For every possible stacking order, find the total number of pizzas that are visible when viewed from above. A pizza is visible if it is larger than every pizza stacked on top of it.

Pizzas of the same size are indistinguishable, so the order among pizzas of the same size is not considered.

Input

The first line contains $N$ , the size of the largest pizza.

The next line contains $a_1$ , $a_2$ , $\cdots$ , $a_N$ separated by spaces, where $a_i$ is the number of pizzas of size $i$ .

Output

Print the sum, over all possible orders, of the number of visible pizzas, modulo $1\,000\,000\,007$ .

Constraints

$1 \leq N \leq 300\,000$
$1 \leq a_i \leq 500\,000$
$\sum a_i \leq 500\,000$

Hint

In the first sample, every possible order and the number of visible pizzas for each order are listed below. Pizzas are written from the top down.

(1, 2, 2): 2
(2, 1, 2): 1
(2, 2, 1): 1

The total number of visible pizzas is $2+1+1=4$ .

Examples2

Example 1
Input
```
2
1 2
```
Expected output
```
4
```
Example 2
Input
```
3
1 1 1
```
Expected output
```
11
```