Time Limit: 10000/5000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

#### Problem Description

Given a array A with N elements, and you can perform the following operation several times: randomly choose two indexes l and r (l < r) and reverse A[l...r] (both inclusive).

After you perform the operation above K times, you randomly choose two indexes l and r (l < r) and calculate the S = sum(A[l...r]) (both inclusive). Now you are to calculate the expected value of S.

If you are not familiar with the "reverse" operation, you can see the following example: If you have a array A = [1, 2, 3, 4], the reversed array of A would be A' = [4, 3, 2, 1].

#### Input

The first line of input file contains an integer T indicating the number of case.

In each test case:

The first line contains two integers N and K. (1 <= N <= 1000, 0 <= K <= 10)

The next line contains N integers which are the elements of array A. (0 <= A[i] <= 1,000,000,000)

#### Output

For each test case:

Output the expected value of S which should accurate to four decimal places.

#### Sample Input

#### Sample Output

#### Source

dut200901102

#### Manager