Yet Another Disappointment: A Matching Problem#12858

Yet Another Disappointment: A Matching Problem

1 second
256 megabytes
Very hard

You are given an odd number . For an array of numbers [a_1, a_2, \ldots, a_n], define its cost as the maximum weight of a perfect matching in the graph on n+1 vertices in which the weight of the edge for i<j is defined as max(a_i, a_{i+1}, \ldots, a_{j-1}).

For example, for the array [1, 30, 15] we have a graph on vertices with the following distances between them:

Here the matching ((1, 2), (3, 4)) has weight , while ((1, 3), (2, 4)) and ((1, 4), (2, 3)) have weight , so the cost of the whole array equals .

You are given an array of length with pairwise distinct elements. Find the sum of the costs of all permutations of this array, modulo 10^9 + 7.

Recall that a perfect matching in a weighted graph on vertices is a set of edges such that every vertex is an endpoint of exactly one edge. The weight of a perfect matching is the sum of the weights of all chosen edges.

Input

The first line contains one integer (1 \leq n \leq 99\,999, is odd) — the length of the array.

The second line contains pairwise distinct integers b_1, b_2, \ldots, b_n (1 \leq b_i \leq 10^8) — the elements of the array.

Output

Print the sum of the costs of all permutations of this array, modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the sample:

  • The costs of the arrays [1, 30, 15] and [15, 30, 1] equal .

  • The costs of the arrays [1, 15, 30], [30, 15, 1], [15, 1, 30], [30, 1, 15] equal .

The sum over all permutations equals 60\cdot 2 + 45\cdot 4 = 300.