Problem Statement :

A function $F(A, k)$ has two arguments, an array of integers A and an integer k and is defined as: You generate all subsequences of array A that are of size k (there are $\binom{size(A)}{k}$ such sequences), then for every sequence you pick the maximum element and sum them (see sample case for more detail). More formally:

$F(A, k) = \displaystyle \sum_{i = 1}^{\binom{size(A)}{k}} \space max_{seq_i}$

Let us define a function $G(A)$ as:

$G(A) = \displaystyle\sum_{1}^{size(A)} F(A, i)$

You are given the array A and have to find the value of the $G(A)$ mod $10^9 + 7$ .

Note: $\binom{n}{k} = \space C^{n}_{k}$

Input Format :

The first line contains an integer N denoting the size of the array A.
The second line contains N integers denoting the elements of the array A.

Output Format :

Print an integer that is equal to $G(A) \space \% \space 10^9 + 7$

Constraints :

$1 \leq N < 2 \times 10^5$
$1 \leq A_i \leq 10^9$
All $A_i$ are unique

Sample Input

3
1 2 3

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Subsequences for k = 1 i.e. subsequences of size 1: $\{1\}, \{2\}, \{3\}$

Subsequences for k = 2 i.e. subsequences of size 2: $\{1, 2\}, \{2, 3\}, \{1, 3\}$

Subsequences for k = 3 i.e. subsequences of size 3: $\{1, 2, 3\}$

$F(A, 1) = max(\{1\}) + max(\{2\}) + max(\{3\}) = 1 + 2 + 3 = 6$

$F(A, 2) = max(\{1, 2\}) + max(\{2, 3\}) + max(\{1, 3\}) = 2 + 3 + 3 = 8$

$F(A, 3) = max(\{1, 2, 3\}) = 3$

$G(A) = F(A, 1) + F(A, 2) + F(A, 3) = 6 + 8 + 3 = 17$