피자 쌓기

크기가 $1$, $2$, $\cdots$, $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, 2, 2): 2개
• (2, 1, 2): 1개
• (2, 2, 1): 1개

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