You have given an array A containing weights of N pizzas. You have to eat exactly 4 pizzas each day. When you eat pizzas of weights X, Y, Z, and W where \(X \ge Y \ge Z \ge W,\) you gain weight equal to Z (i.e. 2nd minimum value of the group), for example- suppose you pick 4 value [7, 4, 3, 3] so you will gain weight 3.

Calculate the maximum total weight you can gainby eating the pizzas optimally each day. As the answer could be very large, print it modulo \(10^9+7\)

Constraints

• \(1 \le N \le 10^5 \\ 1 \le A[i] \le 10^5\)

Input Format

The first line contains an integer, N, denoting the number of elements in A.

Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing Ai.

Output format

Print  a single integer modulo \(10^9+7\)