이진 탐색 게임 timer 30s memory 1024MB

앨리스(Alice)와 밥(Bob)이 이진 탐색 게임(Binary Search game)을 하려고 한다. 게임은 2^\mathbf{L}개의 칸이 일렬로 놓인 보드에서 진행된다. 각 칸에는 1 이상 \mathbf{N} 이하의 정수 하나가 들어 있다. 또한 1번부터 \mathbf{N}번까지 번호가 매겨진 \mathbf{N}장의 카드가 있다. 게임이 시작되기 전에 심판은, 각 카드에 1 이상 \mathbf{M} 이하의 정수 하나를 가능한 \mathbf{M}^\mathbf{N}가지 방법 중 하나로 적어 둔다. 앨리스와 밥은 게임을 시작하기 전에 보드의 각 칸에 들어 있는 정수들과 각 카드에 적힌 정수들을 모두 알고 있다.

게임은 번갈아가며 진행되며 앨리스가 먼저 시작한다. 총 턴 수는 \mathbf{L}이고, 따라서 앨리스는 \lceil \mathbf{L} / 2 \rceil턴, 밥은 \lfloor \mathbf{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라고 하자. 게임의 점수(score)는 X번 카드에 적힌 정수이다. 위 예시에서, 마지막 턴에 앨리스가 [5]를 제거하고 [2]를 남겼다면, 게임의 점수는 심판이 2번 카드에 적어 둔 수가 된다.

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