Binary Search Game

Alice and Bob are going to play the Binary Search game. The game is played on a board made of a single row of $2L$ cells. Each cell contains an integer from 1 to $N$, inclusive. There are also $N$ cards numbered 1 through $N$. Before the game starts, the referee writes an integer from 1 to $M$, inclusive, on each card. There are $M^N$ ways to do this. Alice and Bob know the integers in the cells and on each card before they start playing.

Alice has the first turn. The game has $L$ turns in total, so Alice plays $\lceil L/2 \rceil$ turns and Bob plays $\lfloor L/2 \rfloor$ turns. During a turn, a player can eliminate either the leftmost half or the rightmost half of the remaining cells. For example, let us consider a board that contains the numbers [2,4,1,1,4,5,2,5]. In her first turn, Alice must choose to eliminate one half, leaving either [2,4,1,1] or [4,5,2,5]. If she eliminates the leftmost half and leaves [4,5,2,5], then Bob must choose between leaving [4,5] and [2,5]. If he were to leave [2,5], the game's final turn would have Alice choosing between [2] and [5].

When the game is over, they look at the number X in the only remaining cell. The score of the game is the integer written on card number X. In the example above, if Alice were to eliminate [5] and leave [2] in her final turn, the score of the game would be the number the referee wrote on card number 2.

Alice plays to maximize the score, while Bob plays to minimize it. They are given a fixed board with integers $A_1, A_2, \ldots, A_{2L}$ in its cells. For maximal fairness, they will play $M^N$ games, and the referee will write the integers on the cards differently for each game. That is, for each way of writing integers on the cards, Alice and Bob play exactly one game. Given the game parameters and the fixed board, find the sum of the scores of all those games. Since the sum can be very large, output it modulo the prime $10^9+7$ (1000000007).

The first line contains the number of test cases $T$. Each test case consists of exactly two lines. The first line of each test case contains three integers $N$, $M$, and $L$. The second line contains $2L$ integers $A_1, A_2, \ldots, A_{2L}$, where $A_i$ is the integer in the $i$-th cell from the left.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the sum of the scores of all $M^N$ games, modulo $10^9+7$ (1000000007).

• $1 \le T \le 12$.
• $1 \le L \le 5$.
• $1 \le A_i \le N$ for all $i$.

In Sample Case #1, there are 4 ways to write the integers on the blank cards: [1,1], [1,2], [2,1], and [2,2]. In the first two ways, no matter what Alice chooses on her first turn, Bob can always make the number in the last remaining cell a 1. Card 1 contains a 1, so the scores of those two games are 1. In the last two ways, Alice can start by eliminating the leftmost half, leaving [1,1] for Bob, who then has no choice but to leave [1]. Card 1 has a 2 in these ways, so the score of both games is 2. The sum of all scores is 1+1+2+2=6.