이진 탐색 게임

앨리스와 밥이 이진 탐색 게임을 한다. 게임은 한 줄로 늘어선 $2L$개의 칸으로 이루어진 보드에서 진행된다. 각 칸에는 1 이상 $N$ 이하의 정수가 하나씩 적혀 있다. 또한 1번부터 $N$번까지 번호가 붙은 카드가 $N$장 있다. 게임을 시작하기 전에 심판은 각 카드에 1 이상 $M$ 이하의 정수를 적는다. 이때 가능한 방법은 모두 $M^N$가지이며, 심판은 그중 하나를 고른다. 앨리스와 밥은 게임을 시작하기 전에 칸의 정수와 각 카드에 적힌 정수를 모두 안다.

앨리스가 먼저 한다. 게임은 총 $L$턴이며, 앨리스가 $\lceil L/2 \rceil$턴, 밥이 $\lfloor L/2 \rfloor$턴을 맡는다. 한 턴에서 플레이어는 남은 칸들 중 가장 왼쪽 절반 또는 가장 오른쪽 절반을 지울 수 있다. 예를 들어 보드가 [2,4,1,1,4,5,2,5]라고 하자. 앨리스는 첫 턴에 절반 중 하나를 지워야 하므로 [2,4,1,1] 또는 [4,5,2,5]가 남는다. 앨리스가 왼쪽 절반을 지워 [4,5,2,5]를 남기면, 밥은 [4,5]와 [2,5] 중에서 하나를 남겨야 한다. 밥이 [2,5]를 남겼다면 마지막 턴에 앨리스는 [2]와 [5] 중에서 고른다.

게임이 끝나면 남은 한 칸의 수 X를 본다. 게임의 점수는 카드 X에 적힌 정수이다. 위 예시에서 앨리스가 마지막 턴에 [5]를 지우고 [2]를 남기면, 게임의 점수는 심판이 2번 카드에 적은 수가 된다.

앨리스는 점수를 최대화하고 밥은 점수를 최소화하도록 최적으로 플레이한다. 보드의 칸에는 고정된 정수 $A_1, A_2, \ldots, A_{2L}$이 적혀 있다. 공정성을 위해 두 사람은 $M^N$번의 게임을 하며, 심판은 게임마다 카드에 적는 정수의 방법을 다르게 고른다. 즉 카드에 정수를 적는 방법 하나당 앨리스와 밥은 정확히 한 번의 게임을 한다. 주어진 게임 조건과 고정된 보드에 대해 모든 게임 점수의 합을 구하라. 합이 매우 클 수 있으므로 소수 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 정확히 두 줄로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $L$이 주어진다. 둘째 줄에는 $2L$개의 정수 $A_1, A_2, \ldots, A_{2L}$이 주어지며, $A_i$는 왼쪽에서 $i$번째 칸에 적힌 정수이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 $M^N$번 게임 점수의 합을 $10^9+7$로 나눈 나머지이다.

• $1 \le T \le 12$
• $1 \le L \le 5$
• 모든 $i$에 대해 $1 \le A_i \le N$

샘플 케이스 #1에서 빈 카드에 쓸 수 있는 방법은 [1,1], [1,2], [2,1], [2,2]의 4가지이다. 앞의 두 방법에서는 앨리스가 첫 턴에 무엇을 고르든 밥이 마지막에 남는 수를 1로 만들 수 있다. 카드 1에는 1이 적혀 있으므로 이 두 게임의 점수는 1이다. 뒤의 두 방법에서는 앨리스가 먼저 왼쪽 절반을 지워 [1,1]을 밥에게 넘길 수 있고, 밥은 [1]을 남길 수밖에 없다. 이때 카드 1에는 2가 적혀 있으므로 두 게임의 점수는 모두 2이다. 모든 게임 점수의 합은 1+1+2+2=6이다.