E. 最大历史值

时间限制： 3秒
内存限制： 256 MB

题目描述

给定一个长度为 $n$ 的数组 $a$。定义 $f_a$ 如下：

• 初始时 $f_a = 0$，$M = 1$；
• 对于每个 $2 \le i \le n$，如果 $a_M < a_i$，则令 $f_a = f_a + a_M$，然后令 $M = i$。

计算 $f_a$ 在数组 $a$ 的所有 $n!$ 种排列下的总和，结果对 $10^9 + 7$ 取模。

注意：两个元素若下标不同则视为不同，因此对于每个数组 $a$，恰好有 $n!$ 种排列。

输入

第一行包含一个整数 $n$（$1 \le n \le 1\,000\,000$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出

输出一个整数——$f_a$ 在所有 $n!$ 种排列下的总和，对 $10^9 + 7$ 取模。

样例

样例 1

2
1 3

1

样例 2

3
1 1 2

4

提示

对于第二个样例，所有排列如下（$p$ 为原始数组 $a$ 的下标排列）：

• $p = [1, 2, 3]$：$f_a = 1$
• $p = [1, 3, 2]$：$f_a = 1$
• $p = [2, 1, 3]$：$f_a = 1$
• $p = [2, 3, 1]$：$f_a = 1$
• $p = [3, 1, 2]$：$f_a = 0$
• $p = [3, 2, 1]$：$f_a = 0$

总和为 $4$。