Background

Poor little Bronya is crying and throwing a tantrum because she cannot think of a good idea. Oh, how pitiful.

Description

Bronya wants to create a new DLC for the "Alahato Training Camp Peer Review," but she cannot come up with a good idea.

She currently has $n$ ideas, each with a difficulty value $a_i$, where $1 \le a_i \le m$.

She plans to select one idea from these as the final idea using the following method:

She randomly selects an interval $[l, r]$ from the $\dfrac{n(n+1)}{2}$ possible intervals with equal probability, and then randomly selects an integer $lim$ from $[1, m]$ with equal probability as the difficulty limit.

Then, Bronya chooses an index $x$ such that $i \in [l, r]$ and $a_i \le lim$, selecting the one with the largest $a_i$.

The value $a_x$ will be the final difficulty value. If no such $x$ exists, the final difficulty value is $0$.

Bronya wants to know the expected value of the final difficulty. Please help her.

Since expected value is a noble level-10 algorithm that little Bronya does not know, please output the expected value multiplied by $\dfrac{n \times (n+1) \times m}{2}$.

Input

The first line contains two integers $n$ and $m$, representing the number of ideas and the upper bound of the difficulty values, respectively.

The second line contains $n$ integers, where the $i$-th integer $a_i$ represents the difficulty value of the $i$-th idea.

Output

Output a single integer $ans$, which is the expected value of the final difficulty multiplied by $\dfrac{n \times (n+1) \times m}{2}$.

Examples

Input 1

3 4
1 1 4

Output 1

30

Input 2

10 20
5 19 3 14 2 8 18 7 1 5

Output 2

7535

Note

Consider the six possible intervals: $[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]$.

The expected difficulty values for these are $1, 1, \frac{7}{4}, 1, \frac{7}{4}, 1$, respectively. The final answer is $\dfrac{1+1+\frac{7}{4}+1+\frac{7}{4}+1}{6} \times 6 \times 4 = 30$.

Constraints

For all test cases, $1 \le n \le 1 \times 10^6, 1 \le m \le 1 \times 10^9$.

• Subtask 1 (5pts): $n \le 500$
• Subtask 2 (5pts): $n \le 4000$, depends on Subtask 1.
• Subtask 3 (5pts): $m \le 2$.
• Subtask 4 (20pts): $m \le 50$, depends on Subtask 3.
• Subtask 5 (10pts): $a_i$ are guaranteed to be generated randomly in $[1, m]$, $n \le 5 \times 10^5$.
• Subtask 6 (20pts): $n \le 10^5$, depends on Subtask 1, 2.
• Subtask 7 (35pts): No additional constraints, depends on Subtask 1, 2, 3, 4, 5, 6.