不难想到将所求转化为 $\displaystyle\sum_{\text{长为 n 的排列 p}} \sum_{i = 1}^n [\forall 1 \leq j < i, a_{p_j} \neq a_{p_i}] i$。

显然不同的 $a$ 值对应的下标的贡献不会互相影响。考虑对每个 $a$ 值分别处理。

对于一个出现在 $a$ 中的 $b$，首先，对于所有 $cnt_b$ 个下标，首先我们需要从 $cnt_b$ 中随意选出一个作为第一次出现的下标，再枚举第一次出现的下标 $i$，则其贡献为 $i A_{n - i}^{cnt_b - 1}$；其次，对于剩下的 $n - cnt_b$ 个下标，它们无论怎么排列都与这个 $b$ 本身的贡献无关。于是 $b$ 对答案的总贡献为 $cnt_b (n - cnt_b)! \displaystyle\sum_{i = 1}^{n - (cnt_b - 1)} i A_{n - i}^{cnt_b - 1}$。

直接暴力对每个 $b$ 求其贡献的和的时间复杂度是 $O(n^2 + N)$ 的，显然不能通过。

注意到影响每个 $b$ 的贡献的因素仅有 $cnt_b$ 的值，而由于 $\sum cnt_i = n$，则不同的 $cnt_i$ 的个数是 $O(\sqrt{n})$ 的，于是我们只对每个不同的 $cnt_i$ 暴力计算贡献即可。时间复杂度为 $O(n \sqrt{n} + N)$，但还是不能通过。

考虑对式子本身进行处理，则：

$\displaystyle\sum_{i = 1}^{n - (cnt_b - 1)} i A_{n - i}^{cnt_b - 1} = \sum_{i = cnt_b - 1}^{n - 1} (n - i) A_i^{cnt_b - 1}$

$= (cnt_b - 1)! \displaystyle\sum_{i = cnt_b - 1}^{n - 1} (n - i) C_i^{cnt_b - 1}$

$= (cnt_b - 1)! \displaystyle\sum_{i = cnt_b - 1}^{n - 1} C_i^{cnt_b - 1} \sum_{j = 1}^{n - i} 1$

$= (cnt_b - 1)! \displaystyle\sum_{j = 1}^{n - (cnt_b - 1)} \sum_{i = cnt_b - 1}^{n - j} C_i^{cnt_b - 1}$

$= (cnt_b - 1)! \displaystyle\sum_{j = 1}^{n - (cnt_b - 1)} C_{n - j + 1}^{cnt_b}$

$= (cnt_b - 1)! \displaystyle\sum_{j = cnt_b}^n C_j^{cnt_b}$

$= (cnt_b - 1)! C_{n + 1}^{cnt_b + 1}$。

上面的推导利用了经典结论 $\displaystyle\sum_{i = x}^y C_i^x = C_{y + 1}^{x + 1}$。

再乘上前面的常数 $cnt_b (n - cnt_b)!$ 可以进一步化简为 $\dfrac{(n + 1)!}{cnt_b + 1}$。

至此可以在预处理阶乘和逆元后 $O(1)$ 计算每一项。时间复杂度为 $O(n + N)$。若直接快速幂求逆元则会多一个 $\log$，无法通过所有数据。

代码：

#include <stdio.h>

typedef long long ll;

const int N = 1e7, mod = 1e9 + 7;
int cnt[N + 7];
ll fac[N + 7], inv[N + 7];

inline void init(int n){
	fac[0] = 1;
	for (register int i = 1; i <= n; i++){
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[0] = inv[1] = 1;
	for (register int i = 2; i <= n; i++){
		inv[i] = mod - (mod / i) * inv[mod % i] % mod;
	}
}

inline int read(){
	int ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans;
}

int main(){
	int n = read(), ni = n + 1;
	ll ans = 0;
	init(ni);
	for (register int i = 1; i <= n; i++){
		int a = read();
		cnt[a]++;
	}
	for (register int i = 1; i <= N; i++){
		if (cnt[i] > 0) ans = (ans + inv[cnt[i] + 1]) % mod;
	}
	printf("%lld", ans * fac[ni] % mod);
	return 0;
}