{"raw_statement":[{"iden":"statement","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_ and then set _M_ = _i_.\n\nCalculate the sum of _f__a_ over all _n_! permutations of the array _a_ modulo 109 + 7.\n\nNote: two elements are considered different if their indices differ, so for every array _a_ there are exactly _n_! permutations."},{"iden":"input","content":"The first line contains integer _n_ (1 ≤ _n_ ≤  1 000 000) — the size of array _a_.\n\nSecond line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤  _a__i_ ≤  109)."},{"iden":"output","content":"Print the only integer, the sum of _f__a_ over all _n_! permutations of the array _a_ modulo 109 + 7."},{"iden":"examples","content":"Input\n\n2\n1 3\n\nOutput\n\n1\n\nInput\n\n3\n1 1 2\n\nOutput\n\n4"},{"iden":"note","content":"For the second example all the permutations are:\n\n*   _p_ = \\[1, 2, 3\\] : _f__a_ is equal to 1;\n*   _p_ = \\[1, 3, 2\\] : _f__a_ is equal to 1;\n*   _p_ = \\[2, 1, 3\\] : _f__a_ is equal to 1;\n*   _p_ = \\[2, 3, 1\\] : _f__a_ is equal to 1;\n*   _p_ = \\[3, 1, 2\\] : _f__a_ is equal to 0;\n*   _p_ = \\[3, 2, 1\\] : _f__a_ is equal to 0.\n\nWhere _p_ is the array of the indices of initial array _a_. The sum of _f__a_ is equal to 4."}],"translated_statement":[{"iden":"statement","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$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$)。\n\n请输出一个整数，表示数组 $a$ 的所有 $n!$ 个排列上 $fa$ 的交错和之和，对 $10^9 + 7$ 取模。\n\n对于第二个例子，所有排列为：\n\n其中 $p$ 是初始数组 $a$ 的下标数组。$fa$ 的和等于 $4$。\n\n"},{"iden":"input","content":"第一行包含整数 $n$ ($1 ≤ n ≤ 1 000 000$) —— 数组 $a$ 的大小。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$)。"},{"iden":"output","content":"请输出一个整数，表示数组 $a$ 的所有 $n!$ 个排列上 $fa$ 的交错和之和，对 $10^9 + 7$ 取模。"},{"iden":"examples","content":"输入21 3输出1输入31 1 2输出4"},{"iden":"note","content":"对于第二个例子，所有排列为： $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$。"}],"sample_group":[],"show_order":[],"formal_statement":"**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, n\\} $.  \nFor 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)}\\} $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1\\,000\\,000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute  \n$$\n\\sum_{\\sigma \\in \\mathcal{S}_n} f_a(\\sigma) \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}