Code: Prime Gaming (Hard Version)

#include <stdio.h>
#include <string.h>

#define N 20
#define MD 1000000007

int bcnt[1 << N];

void init() {
    int b;

    for (b = 1; b < 1 << N; b++)
        bcnt[b] = bcnt[b & b - 1] + 1;
}

int main() {
    int t;

    init();
    scanf("%d", &t);
    while (t--) {
        static char good[N], dp[1 << N + 1];
        static int kk[N + 1];
        int n, m, k, l, i, b, a, c, p, x, ans;

        scanf("%d%d%d", &n, &m, &k);
        memset(good, 0, n * sizeof *good);
        while (k--) {
            scanf("%d", &i), i--;
            good[i] = 1;
        }
        dp[2] = 0, dp[3] = 1;
        for (l = 2; l <= n; l++) {
            c = (n - l + 1) % 2;
            for (b = 1 << l; b < 1 << l + 1; b++) {
                dp[b] = c ^ 1;
                for (i = 0; i < l; i++)
                    if (good[i] &&
                        (dp[b >> i + 1 << i | b & (1 << i) - 1] == c)) {
                        dp[b] = c;
                        break;
                    }
            }
        }
        memset(kk, 0, (n + 1) * sizeof *kk);
        for (b = 0; b < 1 << n; b++)
            if (dp[b | 1 << n])
                kk[bcnt[b]]++;
        ans = 0;
        for (a = 1; a <= m; a++) {
            p = 1, x = 0;
            for (c = 0; c <= n; c++) {
                x = ((long long)x * (a - 1) + (long long)kk[c] * p) % MD;
                p = (long long)p * (m - a + 1) % MD;
            }
            ans = (ans + x) % MD;
        }
        printf("%d\n", ans);
    }
    return 0;
}