CodeChef submission 136761 (C++ 4.0.0-8) plaintext list. Status: TLE, problem SNCK03, contest SNACKDWN. By SlodziakiUWr (SlodziakiUWr), 2009-11-21 23:55:16.
#include <cstdio>
#include <vector>
 
#define MOD 1000000007
 
std::vector<int> BINOM[10001];
 
inline int modulo (int a)
{
    if (a >= MOD) a-= MOD;
    return a;
}
 
inline int npok (int n, int k)
{
    if (k < 0) return 0;
    if (k + k > n) k = n - k;
 
    if (k == 0) return 1;
 
    if (n % 3 == 0) return BINOM[n/3][k];
    else return modulo (npok(n-1,k) + npok(n-1,k-1));
}
 
void precompute ()
{
    BINOM[0].push_back (1);
 
    for (int i = 3; i <= 20000; i += 3)
    {
        int current = i / 3;
        BINOM[current].resize ( 1 + i / 2);
        BINOM[current][0] = 1;
        BINOM[current][1] = i;
        for (int j = 2; j + j < i; ++j)
        {
            long long x = npok(i-3,j - 3);
            long long y = 3LL * npok(i-3,j - 2);
            long long z = 3LL * npok(i-3,j - 1);
            long long t = npok(i-3,j);
            BINOM[current][j] = (x + y + z + t) % MOD;
        }
    }
}
 
int n, k;
int A[30];
int DP[23][32][21000];
 
int gogo (int a, int b, int c)
{
    if (a + 1 == b) return 1;
    else
    {
        if (DP[a][b][c] == -1)
        {
            DP[a][b][c] = 0;
 
            if (a % 2 == b % 2)
            {
                // przypadki ze tylko dzielimy
                long long ret = 0;
                for (int h = a + 1; h < b; h += 2)
                {
                    int elements = A[b] - A[a] + 1 - c - 1 - (b!=k-1) - (a!=0);
                    int howmany = A[h] - A[a] + 1 - 1 - c - (a!=0);
                    int aa = gogo (a,h,c);
                    int bb = gogo (h,b,0);
                    int cc = npok (elements,howmany);
                    ret += cc * (((long long)(aa) * bb) % MOD);
        			if (ret > 1000000000000000000LL) ret %= MOD;
                }
                DP[a][b][c] = ret % MOD;
            }
            else
            {
                // przypadki ze dzielimy i odcinamy przycinamy prefiks
                long long ret = 0;
 
                // dzielimy
                for (int h = a + 2; h < b; h += 2)
                {
                    int elements = A[b] - A[a] + 1 - c - 1 - (b!=k-1) - (a!=0);
                    int howmany = A[h] - A[a] + 1 - 1 - c - (a!=0);
                    int aa = gogo (a,h,c);
                    int bb = gogo (h,b,0);
                    int cc = npok (elements,howmany);
                    ret += cc * (((long long)(aa) * bb) % MOD);
        			if (ret > 1000000000000000000LL) ret %= MOD;
                }
                // przycinamy prefiks
                if (A[a] + c + (a != 0) < A[a + 1])
                    ret += gogo (a,b,c + 1);
 
                DP[a][b][c] = ret % MOD;
            }
        }
 
        return DP[a][b][c];
    }
}
 
void doit ()
{
 
    scanf ("%d %d", &n, &k);
    for (int i = 0; i < k; ++i)
    {
        scanf ("%d", &A[i]);
        A[i]--;
    }
 
    for (int i = 0; i < k; ++i)
        for (int j = i + 1; j < k; ++j)
            for (int h = 0; h < A[j] - A[i] + 1; ++h)
                DP[i][j][h] = -1;
 
    printf ("%d\n", gogo (0, k - 1, 0));
}
 
int main ()
{
    precompute ();
 
 
    int tests;
    scanf ("%d", &tests);
    while (tests--) doit ();
 
 
    return 0;
}