Alice và Bob chơi trò Binary Search trên một bảng một hàng gồm \(2^L\) ô. Mỗi ô chứa một số nguyên từ \(1\) đến \(N\). Ngoài ra có \(N\) lá bài đánh số \(1\) đến \(N\). Trước mỗi ván, trọng tài ghi lên mỗi lá một số từ \(1\) đến \(M\), theo một trong \(M^N\) cách. Alice và Bob biết mọi số trên bảng và trên bài trước khi chơi.

Hai người luân phiên, Alice đi trước. Có tổng cộng \(L\) lượt: Alice đi \(\lceil L/2\rceil\) lượt, Bob đi \(\lfloor L/2\rfloor\) lượt. Mỗi lượt, người chơi loại nửa trái hoặc nửa phải của các ô còn lại.

Ví dụ, với bảng \([2,4,1,1,4,5,2,5]\), Alice đầu tiên phải để lại \([2,4,1,1]\) hoặc \([4,5,2,5]\). Nếu cô loại nửa trái và để \([4,5,2,5]\), Bob chọn giữa \([4,5]\) và \([2,5]\). Nếu Bob để \([2,5]\), lượt cuối Alice chọn giữa \([2]\) và \([5]\).

Khi kết thúc, gọi \(X\) là số trong ô duy nhất còn lại. Điểm là số trọng tài ghi trên lá bài số \(X\). Trong ví dụ, nếu Alice loại \([5]\) và để \([2]\), điểm là số trên lá bài \(2\).

Alice chơi tối ưu để tối đa hóa điểm, Bob chơi tối ưu để tối thiểu hóa. Bảng cố định chứa \(A_1,\ldots,A_{2^L}\). Để công bằng tối đa, họ chơi đủ \(M^N\) ván, mỗi ván dùng một cách ghi số khác nhau lên các lá; mỗi cách xuất hiện đúng một lần. Hãy tính tổng điểm của mọi ván, lấy modulo số nguyên tố \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ đúng hai dòng: dòng đầu chứa \(N,M,L\); dòng sau chứa \(2^L\) số \(A_1,\ldots,A_{2^L}\) từ trái sang phải.

Dữ liệu ra

Với mỗi bộ, in Case #x: y, trong đó \(y\) là tổng điểm của \(M^N\) ván modulo \(1000000007\).

Ràng buộc

• \(1\le T\le12\); \(1\le L\le5\); \(1\le A_i\le N\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le N\le8\), \(1\le M\le100\).
• Test Set 2 (Hidden Verdict): \(1\le N\le32\), \(1\le M\le10^9\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2 2
2 1 1 1
4 3 2
3 1 1 4
5 100 3
2 4 1 1 4 5 2 5

Case #1: 6
Case #2: 144
Case #3: 991661422

Nguồn

Google Code Jam 2021, Vòng 3, bài Binary Search Game.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.