← 返回题目列表

Codeforces · 938/E

E. 最大历史记录

中文机器翻译题面 查看原题

给定一个长度为 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。