Help Prapor#11125
Prapor is not in the mood for jokes, he decided to take part in the contest. Just help him solve the problem. Consider an array of numbers, where is odd. Let's build a complete weighted graph, that will have n + 1 vertices. The weight of the edge between vertices and (1 \le u < v \le n) is equal to the maximum from a_u, a_{u+1}, ..., a_{v-1}. The cost of the array is the maximum weight of an ideal matching in the constructed graph. An ideal matching is a matching that covers all vertices.
You are given an array consisting of distinct integers. Calculate the sum of the costs of all permutations of the array modulo .
The first line contains one odd integer (1 \le n \le 10^5) - the length of the array . The second line contains distinct integers a_1, a_2, ..., a_n (1 \le a_i \le 10^8).
Print a single number - the sum of the costs of all permutations of the array modulo .
Пример 1