It's time for your school class to elect its class officers for the year.
These officers will have the honour of representing the class and will hold
various responsibilities. The position of class treasurer is particularly
appealing to some of the more organized and mathematically-inclined students,
especially two rivals, Amy and Betty. They've both been running strong
campaigns, to the point that no other feasible candidates remain.

A democratic vote to elect the class treasurer is about to take place! Each of
the **N** students in the class will cast one vote, for either Amy or Betty.
The students have IDs numbered from 1 to **N**, and student _i_ is currently
planning on voting for either Amy (if **Vi** = "A") or Betty (if **Vi** =
"B").

Your teacher, Mr. X, has some "novel" ideas about how elections should work.
Perhaps in an effort to teach your class a statistics lesson, he will organize
the election as follows. He'll consider the set of all **N***(**N**+1)/2
possible non-empty contiguous sets of student IDs, and will select one at
random. Each set will have an equal chance of being selected. He'll refer to
this as the "representative set" of students. He will also announce a
threshold of victory, **K**. He'll then tally up the number of votes for Amy
and Betty amongst those students — let these vote counts be **a** and **b**
respectively. If **a** > **b** \+ **K**, then Amy will win. If **b** > **a**
\+ **K**, then Betty will win. Otherwise, if |**a** \- **b**| ≤ **K**, then it
will be a draw (neither candidate will win, and the class will be left without
a treasurer).

Amy has grown concerned about how the election will turn out, so she's
enlisted your help in potentially swaying some of your classmates' opinions.
She's tasked you with ensuring that, no matter which representative set gets
chosen, Betty cannot possibly win (in other words, either Amy will win or
neither candidate will win). To do so, you may pay 0 or more students to
change their vote from their current candidate to the other one. Student _i_
requires 2i dollars to be influenced in this fashion. You must finish paying
students off _before_ you know what the representative set will be.

What's the minimum possible cost required to guarantee that Betty cannot
possibly win and become the class treasurer? As this cost may be large, output
it modulo 1,000,000,007. Note that you must minimize the actual cost, rather
than minimizing the resulting value of the cost after it's taken modulo
1,000,000,007.

### Input

Input begins with an integer **T**, the number of elections. For each
election, there are two lines. The first line contains the space-separated
integers **N** and **K**. The second line contains the **N** characters **V1**
through **VN**.

### Output

For the _i_th election, print a line containing "Case #_i_: " followed by 1
integer, the minimum possible cost (in dollars) required to guarantee that
Betty cannot become the class treasurer, modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 200
1 ≤ **N** ≤ 1,000,000
0 ≤ **K** ≤ **N**

### Explanation of Sample

In the first case, if you do nothing, then Betty may win (if the
representative set either consists of only student 1 or only student 4). You
should pay students 1 and 4 to each vote for Amy instead of Betty, for a cost
of $2 + $16 = $18. Amy will then be guaranteed to win for any choice of
representative set.

In the second case, you don't need to pay any students to change their minds —
either Amy will win, or it will be a draw.

In the third case, you should pay student 2 $4 to change their vote to Amy.