피자 쌓기

크기가 $1$, $2$, $\cdots$, $N$인 피자가 각각 $a_1$, $a_2$, $\cdots$, $a_N$개씩 있다. 이 피자들을 중심이 서로 겹치도록 쌓으려고 한다.

이때 가능한 모든 순서에 대해, 위에서 내려다봤을 때 보이는 피자의 개수의 합을 구해보자. 어떤 피자가 "보인다"는 것은, 그 피자 위에 쌓인 모든 피자들보다 크다는 것이다.

크기가 같은 피자들은 구분되지 않는다. 즉 크기가 같은 피자들끼리의 순서는 고려하지 않는다.

입력은 다음과 같이 주어진다.

$N$

$a_1$ $a_2$ $\cdots$ $a_N$

첫째 줄에 가장 큰 피자의 크기 $N$이 주어진다.

다음 줄에는 크기가 $i$인 피자의 개수 $a_i$가 공백으로 구분되어 주어진다.

가능한 모든 순서에 대해, 위에서 내려다봤을 때 보이는 피자의 개수의 합을 $1\,000\,000\,007$으로 나눈 나머지를 출력한다.

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

1번 예제에서 가능한 모든 순서와 각각의 경우에서 보이는 피자의 수는 다음과 같다. 위에 있는 피자부터 순서대로 표기하였다.

• (1, 2, 2): 2개
• (2, 1, 2): 1개
• (2, 2, 1): 1개

보이는 피자 개수의 합은 $2+1+1=4$개이다.