WXHCoder Inversion Expectation

In the mystical monastery led by mcfx, an ancient membrane array is used to summon the legendary WXH. After preparations and amidst the clatter of keyboards, a strange login screen appears with the following challenge:

Given a permutation of length n and k operations, where each operation consists of swapping two distinct numbers chosen uniformly at random, compute the expected number of inversion pairs multiplied by \(\binom{n}{2}^k\). The symbol \(\binom{n}{2}\) denotes the number of ways to choose 2 objects from n.

Note that the initial permutation has an inversion count defined as the number of pairs \((i,j)\) with \(i<j\) and \(p[i] > p[j]\). In each operation, if the pair at positions \(i\) and \(j\) is not involved in the swap then its order remains; if both indices are involved the inversion status flips; and if exactly one of the two positions is swapped, the new pair is equally likely to be an inversion or not (i.e. probability 1/2). By linearity of expectation one may show that for any fixed pair (with initial indicator \(a\) being 0 or 1) the expected value after one operation follows the recurrence

[ v_{k+1} = \frac{n-4}{n} ; v_k + \frac{1}{n-1}, \quad \text{with } v_0 = a. ]

This recurrence has the closed‐form solution

[ v_k = a\left(\frac{n-4}{n}\right)^k + \frac{n}{4(n-1)}\Bigl(1-\left(\frac{n-4}{n}\right)^k\Bigr). ]

Summing over all \(\binom{n}{2}\) pairs and then multiplying by \(\binom{n}{2}^k\) we obtain the final answer

[ \text{Answer} = \binom{n}{2}^k \left[\text{Inv} \cdot \left(\frac{n-4}{n}\right)^k + \binom{n}{2}\cdot \frac{n}{4(n-1)} \Bigl(1-\left(\frac{n-4}{n}\right)^k\Bigr)\right], ]

where \(\text{Inv}\) is the inversion count of the initial permutation. For the purposes of this problem, since the parameters n and k can be very huge, you only need to solve the problem for small values of n and k. Print the result as a floating–point number with exactly 6 digits after the decimal point.

inputFormat

The first line contains two integers n and k (1 ≤ n, k ≤ 10⁶ in the test cases to be evaluated). The second line contains n distinct integers representing a permutation of the numbers from 1 to n.

outputFormat

Output a single line containing the expected number of inversion pairs after performing k random swap operations multiplied by \(\binom{n}{2}^k\). The answer should be printed as a floating-point number with exactly 6 digits after the decimal point.

sample

3 1
3 1 2

2.500000