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≥Y≥Z≥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 109+7
Constraints
- 1≤N≤1051≤A[i]≤105
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 109+7
Pizza weights are [1,3,4,1,5,1,5,3]. You can eat [1,1,1,3] and [3,4,5,5] in batches and gain 1 + 4 = 5 weight.
