English · Original
Chinese · Translation
Formal · Original
You are given an array _a_ of length _n_. We define _f__a_ the following way:
* Initially _f__a_ = 0, _M_ = 1;
* for every 2 ≤ _i_ ≤ _n_ if _a__M_ < _a__i_ then we set _f__a_ = _f__a_ + _a__M_ and then set _M_ = _i_.
Calculate the sum of _f__a_ over all _n_! permutations of the array _a_ modulo 109 + 7.
Note: two elements are considered different if their indices differ, so for every array _a_ there are exactly _n_! permutations.
## Input
The first line contains integer _n_ (1 ≤ _n_ ≤ 1 000 000) — the size of array _a_.
Second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).
## Output
Print the only integer, the sum of _f__a_ over all _n_! permutations of the array _a_ modulo 109 + 7.
[samples]
## Note
For the second example all the permutations are:
* _p_ = \[1, 2, 3\] : _f__a_ is equal to 1;
* _p_ = \[1, 3, 2\] : _f__a_ is equal to 1;
* _p_ = \[2, 1, 3\] : _f__a_ is equal to 1;
* _p_ = \[2, 3, 1\] : _f__a_ is equal to 1;
* _p_ = \[3, 1, 2\] : _f__a_ is equal to 0;
* _p_ = \[3, 2, 1\] : _f__a_ is equal to 0.
Where _p_ is the array of the indices of initial array _a_. The sum of _f__a_ is equal to 4.
你被给定一个长度为 $n$ 的数组 $a$。我们定义 $fa$ 如下：
计算 $fa$ 在数组 $a$ 的所有 $n!$ 个排列上的交错和之和，对 $10^9 + 7$ 取模。
注意：如果两个元素的下标不同，则认为它们不同，因此对于每个数组 $a$，恰好有 $n!$ 个排列。
第一行包含整数 $n$ ($1 ≤ n ≤ 1 000 000$) —— 数组 $a$ 的大小。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$)。
请输出一个整数，表示数组 $a$ 的所有 $n!$ 个排列上 $fa$ 的交错和之和，对 $10^9 + 7$ 取模。
对于第二个例子，所有排列为：
其中 $p$ 是初始数组 $a$ 的下标数组。$fa$ 的和等于 $4$。
## Input
第一行包含整数 $n$ ($1 ≤ n ≤ 1 000 000$) —— 数组 $a$ 的大小。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$)。
## Output
请输出一个整数，表示数组 $a$ 的所有 $n!$ 个排列上 $fa$ 的交错和之和，对 $10^9 + 7$ 取模。
[samples]
## Note
对于第二个例子，所有排列为： $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$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array $ a = (a_1, a_2, \dots, a_n) $.
Let $ \mathcal{S}_n $ denote the symmetric group of all $ n! $ permutations of $ \{1, 2, \dots, n\} $.
For a permutation $ \sigma \in \mathcal{S}_n $, define $ f_a(\sigma) = \sum_{i=1}^n \max\{a_{\sigma(1)}, a_{\sigma(2)}, \dots, a_{\sigma(i)}\} $.
**Constraints**
1. $ 1 \leq n \leq 1\,000\,000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute
$$
\sum_{\sigma \in \mathcal{S}_n} f_a(\sigma) \mod (10^9 + 7)
$$
API Response (JSON)
{
"problem": {
"name": "E. Max History",
"description": {
"content": "You are given an array _a_ of length _n_. We define _f__a_ the following way: * Initially _f__a_ = 0, _M_ = 1; * for every 2 ≤ _i_ ≤ _n_ if _a__M_ < _a__i_ then we set _f__a_ = _f__a_ + _a__M_ an",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF938E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an array _a_ of length _n_. We define _f__a_ the following way:\n\n* Initially _f__a_ = 0, _M_ = 1;\n* for every 2 ≤ _i_ ≤ _n_ if _a__M_ < _a__i_ then we set _f__a_ = _f__a_ + _a__M_ an...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个长度为 $n$ 的数组 $a$。我们定义 $fa$ 如下：\n\n计算 $fa$ 在数组 $a$ 的所有 $n!$ 个排列上的交错和之和，对 $10^9 + 7$ 取模。\n\n注意：如果两个元素的下标不同，则认为它们不同，因此对于每个数组 $a$，恰好有 $n!$ 个排列。\n\n第一行包含整数 $n$ ($1 ≤ n ≤ 1 000 000$) —— 数组 $a$ 的大小。\n\n第二行包含 $n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array $ a = (a_1, a_2, \\dots, a_n) $. \nLet $ \\mathcal{S}_n $ denote the symmetric group of all $ n! $ permutations of $ \\{1, 2, \\dots...",
"is_translate": false,
"language": "Formal"
}
]
}