Max History

我们定义 $f(a)$ 为： 1. 开始时，$f(a)=0$，$M=1$。 2. 对于每个 $2\le i\le n$,如果 $a_M<a_i$，那么 $f(a)=f(a)+a_M$，$M\gets i$。 现在对于一个给定的数组 $a$，求其所有排列的 $f(a)$ 之和，答案对 $10^9+7$ 取模。 **注意：** 如果两个元素的索引不同，那么它们被认为是不同的，因此对于每个数组 $a$，都恰好有 $n!$ 排列。

You are given an array $ a $ of length $ n $ . We define $ f_{a} $ the following way: - Initially $ f_{a}=0 $ , $ M=1 $ ; - for every $ 2<=i<=n $ if $ a_{M}<a_{i} $ then we set $ f_{a}=f_{a}+a_{M} $ and then set $ M=i $ . Calculate the sum of $ f_{a} $ over all $ n! $ permutations of the array $ a $ modulo $ 10^{9}+7 $ . Note: two elements are considered different if their indices differ, so for every array $ a $ there are exactly $ n! $ permutations.

The first line contains integer $ n $ ( $ 1<=n<=1\ 000\ 000 $ ) — the size of array $ a $ . Second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ).

Print the only integer, the sum of $ f_{a} $ over all $ n! $ permutations of the array $ a $ modulo $ 10^{9}+7 $ .

2
1 3

1

3
1 1 2

4

For the second example all the permutations are: - $ p=[1,2,3] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[1,3,2] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[2,1,3] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[2,3,1] $ : $ f_{a} $ is equal to $ 1 $ ; - $ p=[3,1,2] $ : $ f_{a} $ is equal to $ 0 $ ; - $ p=[3,2,1] $ : $ f_{a} $ is equal to $ 0 $ . Where $ p $ is the array of the indices of initial array $ a $ . The sum of $ f_{a} $ is equal to $ 4 $ .