A false witness that speaketh lies!

You are given a sequence containing *n* integers. There is a variable *res* that is equal to 0 initially. The following process repeats *k* times.

Choose an index from 1 to *n* uniformly at random. Name it *x*. Add to *res* the multiply of all *a*<sub class="lower-index">*i*</sub>'s such that 1 ≤ *i* ≤ *n*, but *i* ≠ *x*. Then, subtract *a*<sub class="lower-index">*x*</sub> by 1.

You have to find expected value of *res* at the end of the process. It can be proved that the expected value of *res* can be represented as an irreducible fraction <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b795551c4ba5b501281e7063ac11feb87c7f234f.png" style="max-width: 100.0%;max-height: 100.0%;"/>. You have to find <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/e6387465bd69e039151b5354601d2488d4ec2099.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 5000, 1 ≤ *k* ≤ 10<sup class="upper-index">9</sup>) — the number of elements and parameter *k* that is specified in the statement.

The second line contains *n* space separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
none
2 1
5 5
5
1 10
80
10
2 2
0 0
500000003
9 4
0 11 12 9 20 7 8 18 2
169316356
5 1
14 2 0 0 1
0
2 4
0 16
29
7 2
0 9 4 0 7 14 4
999999431
10 3
12 15 19 16 19 0 4 3 5 11
727205525
3 3
18 7 17
222222747
8 3
20 15 1 4 20 16 6 12
15570669
7 405871919
4 4 12 5 7 10 10
873805235
2 753394402
3 15
220969232
2 34825250
10 12
384515834
5 585751779
18 17 6 12 11
524262917
7 473906062
12 4 11 13 6 5 14
355582323
1 633497352
18
633497352
10 971821326
13 5 5 10 14 20 16 9 4 12
188083285
1 67560349
1
67560349
9 175070971
14 13 11 8 11 3 5 3 5
323903514
6 820579681
15 1 1 9 1 11
692700809
t = int(input())
for index in range(t): 
    n = int(input())
    arr = [int(i) for i in input().split()]
    enArr = list(enumerate(arr,0))
    enArr.sort(lambda x: x[1])
    indexRef = [x[1] for x in enArr]
    tempOut = []
    for i,s in enArr:
        
        place = indexRef.index(s)
        
        if place:
            lil = indexRef[:place]
        else: 
            lil = []
        
        big = indexRef[place:]
       
        tempOut.append((i,str( sum(big) +(len(lil) - len(big))*s - sum(lil) + len(arr))))
    tempOut.sort(lambda x: x[0])
    out = [str(x[1]) for x in tempOut]
    
    print('out', ' '.join(out))