给定一个长度为 n 的数组 a。我们按以下方式定义 fa:
- 初始 fa = 0,M = 1;
- 对于每2 ≤ i ≤ n,如果aM < ai,那么我们设置fa = fa + aM,然后设置M = i。
计算所有n的fa之和!数组 a 以 109 + 7 为模的排列。
注意:如果两个元素的索引不同,则它们被视为不同,因此对于每个数组 a 正好有 n!排列。
输入
第一行包含整数 n (1 ≤ n ≤ 1 000 000) — 数组 a 的大小。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。
输出
打印唯一的整数,所有 n 的 fa 之和!数组 a 以 109 + 7 为模的排列。
示例
输入 #1
2 1 3
输出 #1
1
输入 #2
3 1 1 2
输出 #2
4
注意
对于第二个示例,所有排列都是:
- p = [1, 2, 3]:fa等于1;
- p = [1, 3, 2]:fa等于1;
- p = [2, 1, 3] : fa 等于 1;
- p = [2, 3, 1] : fa 等于 1;
- p = [3, 1, 2] : fa 等于 0;
- p = [3, 2, 1] : fa 等于 0。
其中 p 是初始数组 a 的索引数组。 fa 之和等于 4。