Copy Duck

This is a story of a young and kind-hearted man, Dengklek. Dengklek is also a diligent and hard-working man; he owns N duck farms (each with Ai ducks in it) and attends them every day. On one peaceful day, a weird talking raccoon comes out of nowhere and visits Dengklek. The raccoon claimed that he (the raccoon) came from the future and was sent by Dengklek's great-great-grandson to help Dengklek. Apparently, the raccoon is a cat, but being blue colored and no ears, it's hard to believe (so, let's just stick to raccoon for a while).

The raccoon has an amazing device called Copy Mirror; it's function is ... to duplicate (make 2 exact copies: the original and the copy) anything! Dengklek has to choose K farms, and the raccoon will use the device to duplicate the number of ducks inside each chosen farm. Any farm can be repeatedly chosen, and the device will be used on that farm as many times as it was chosen. Note that when the device is used after the first time in a same farm, then the duplicated ducks from any previous duplication is also duplicated.

For example, let N = 5, A1..5 = {7, 5, 8, 4, 9}, and K = 3.

Being a talented businessman, Dengklek awares that too many ducks may disrupt the duck price's stability. However, he also doesn't want to reject the raccoon's proposal and make his great-great-grandson upset. Thus, he should choose K farms such that the total number of ducks in all farms after being duplicated is minimized. In the above example, the fourth scenario, (1, 2, 4), corresponds to the optimal strategy with total ducks of 14 + 10 + 8 + 8 + 9 = 49.

Your task in this problem is to help Dengklek to choose the farms such that the total number of ducks in all farms after being duplicated is minimized. You only need to output the resulting total number of ducks. As the output can be very large, modulo the output by 1,000,000,007.

Input

Input begins with an integer: T (1 ≤ T ≤ 50) denoting the number of cases.

Each case contains the following input block: Each case begins with two integer: N K (1 ≤ N ≤ 50,000; 0 ≤ K ≤ 1,000,000,000) denoting the number of farms and duplications, respectively. The next line contains N integers Ai (0 ≤ Ai ≤ 1,000,000,000) denoting the number of ducks in each farm.

Output

For each case, output in a line "Case #X: Y" where X is the case number (starts from 1) and Y is the output for the respective case modulo 1,000,000,007.

Examples

inputExample #1
4
5 3
7 5 8 4 9
3 2
2 3 4
1 1000000000
1
2 1
500000004 10
output
Case #1: 49
Case #2: 14
Case #3: 140625001
Case #4: 500000024
explanation

Case 1: This is the example given in the problem statement.

Case 2: The chosen farms is (1, 2).

Case 3: The chosen farms is (1, 1, 1, ...). There is only one way to do it, so the output should be 1 × 21000000000 modulo 1000000007.

Case 4: There are only two possible choices: (1) or (2). (1) will cause the total ducks become 1000000018, while (2) will cause the total ducks become 500000024; (2) is better because it leads to fewer ducks.



End of Problem