이진 탐색 게임

Alice와 Bob은 Binary Search 게임을 하려고 한다. 게임은 한 줄로 늘어선 $2^\mathbf{L}$개의 칸으로 이루어진 보드에서 진행된다. 각 칸에는 $1$ 이상 $\mathbf{N}$ 이하의 정수가 들어 있다. 또한 $1$부터 $\mathbf{N}$까지 번호가 매겨진 $\mathbf{N}$장의 카드가 있다. 게임을 시작하기 전에 심판은 가능한 $\mathbf{M}^\mathbf{N}$가지 방법 중 하나로 각 카드에 $1$ 이상 $\mathbf{M}$ 이하의 정수를 하나씩 적는다. Alice와 Bob은 게임을 시작하기 전에 각 칸과 각 카드에 적힌 정수를 알고 있다.

게임은 Alice가 먼저 시작하여 번갈아 가며 진행한다. 턴은 총 $\mathbf{L}$번이며, 이는 Alice가 $\lceil \mathbf{L} / 2 \rceil$번, Bob이 $\lfloor \mathbf{L} / 2 \rfloor$번의 턴을 진행한다는 뜻이다. 자신의 턴에 플레이어는 남은 칸의 왼쪽 절반이나 오른쪽 절반 중 하나를 제거할 수 있다. 예를 들어, 숫자 $[2, 4, 1, 1, 4, 5, 2, 5]$이 들어 있는 보드를 생각해 보자. 첫 턴에 Alice는 한쪽 절반을 제거하여 $[2, 4, 1, 1]$ 또는 $[4, 5, 2, 5]$ 중 하나를 남겨야 한다. Alice가 왼쪽 절반을 제거하여 $[4, 5, 2, 5]$을 남기면, Bob은 $[4, 5]$을 남길지 $[2, 5]$을 남길지 선택해야 한다. Bob이 $[2, 5]$을 남긴다면, 게임의 마지막 턴에는 Alice가 $[2]$과 $[5]$ 중 하나를 선택하게 된다.

게임이 끝나면 유일하게 남은 칸의 숫자 $X$을 확인한다. 게임의 점수는 $X$번 카드에 적힌 정수이다. 위 예시에서 Alice가 마지막 턴에 $[5]$을 제거하고 $[2]$을 남긴다면, 게임의 점수는 심판이 $2$번 카드에 적은 숫자가 된다.

Alice는 게임의 점수를 최대화하도록 최적으로 플레이하고, Bob은 점수를 최소화하도록 최적으로 플레이한다. 두 사람에게는 각 칸에 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots \mathbf{A_{2^L}}$이 들어 있는 고정된 보드가 주어진다. 공정성을 최대한 보장하기 위해 두 사람은 $\mathbf{M}^\mathbf{N}$번의 게임을 하며, 심판은 매 게임마다 카드에 정수를 적는 서로 다른 방법을 선택한다. 즉, 카드에 정수를 적는 각각의 가능한 방법마다 Alice와 Bob이 정확히 한 번의 게임을 진행한다. 게임의 매개변수와 고정된 보드의 내용이 주어질 때, 이 모든 게임의 점수 합을 구하라. 출력값이 매우 클 수 있으므로, 결과를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지만 출력한다.

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 12$. $1 \le \mathbf{L} \le 5$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le \mathbf{N}$.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{N} \le 8$. $1 \le \mathbf{M} \le 100$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{N} \le 32$. $1 \le \mathbf{M} \le 10^9$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정확히 두 줄로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{L}$이 주어진다. 둘째 줄에는 $2^{\mathbf{L}}$개의 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_{2^L}}$가 주어지며, $\mathbf{A_i}$은 보드의 왼쪽에서 $i$번째 칸에 들어 있는 정수이다.

각 테스트 케이스마다 Case #$x$: $y$을 한 줄에 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$은 $\mathbf{M}^{\mathbf{N}}$번의 모든 게임의 점수 합을 소수 $10^9+7$ ($1000000007$)로 나눈 나머지이다.

샘플 케이스 #1에서 빈 카드에 정수를 적는 방법은 $[1, 1]$, $[1, 2]$, $[2, 1]$, $[2, 2]$의 $4$가지이다. 처음 두 방법에서는 Alice가 첫 턴에 무엇을 선택하더라도 Bob은 마지막에 남는 칸의 숫자를 항상 $1$로 만들 수 있고, $1$번 카드에는 $1$이 들어 있으므로 이 두 게임의 점수는 $1$이다. 마지막 두 방법에서는 Alice가 보드의 왼쪽 절반을 제거하는 것으로 시작하여 Bob에게 $[1, 1]$을 남길 수 있으며, Bob은 결국 $[1]$을 남길 수밖에 없다. 이 방법들에서는 $1$번 카드에 $2$이 적혀 있으므로 두 게임의 점수는 모두 $2$이다. 따라서 모든 점수의 합은 $1+1+2+2=6$이다.