题目背景

小 L 准备乘电梯上楼。

题目描述

有 $n$ 个人（包括小 L）要进电梯，而且人们进电梯的顺序与电梯内的烦躁度有关。

具体地，对于一个长为 $n$ 的排列 $p$，表示第 $p_1, p_2, \cdots, p_n$ 个人依次进入电梯，电梯最初没有任何一个表示楼层的数字按钮被按过，对于第 $p_i$ 个人，如果他发现表示自己要去的楼层 $a_{p_i}$ 的数字按钮已经被按过了，他将直接进入电梯；否则，他将按下按钮，且电梯内的烦躁度增加 $i$。

他对此感到好奇，于是他想问你对于所有可能的表示进电梯顺序的排列 $p$，电梯内烦躁度的和。

由于结果可能很大，你只需要求出结果对 $10^9 + 7$ 取模的值。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

输出格式

一行，一个整数，表示所求的值。

4
1 2 2 3

160

提示

本题输入量较大，请采用较快的输入输出方式。最大输入量约 75MB。

对于 $10\%$ 的数据，$1 \leq n \leq 10$；

对于 $30\%$ 的数据，$1 \leq n \leq 100$；

对于 $50\%$ 的数据，$1 \leq n \leq 10^3$；

对于 $70\%$ 的数据，$1 \leq n \leq 10^5$；

对于 $90\%$ 的数据，$1 \leq n \leq 10^6$；

对于 $100\%$ 的数据，$1 \leq n, a_i \leq 10^7$。