CodeChef submission 136604 (C++ 4.3.2) plaintext list. Status: RE, problem SNCK03, contest SNACKDWN. By SlodziakiUWr (SlodziakiUWr), 2009-11-21 23:33:28.
#include <cstdio>
#include <vector>
 
#define MOD 1000000007
 
std::vector<int> BINOM[20001];
 
inline int modulo (int a)
{
    if (a >= MOD) a-= MOD;
    return a;
}
 
inline int npok (int n, int k)
{
    if (k + k > n) k = n - k;
    return BINOM[n][k];
}
 
void precompute ()
{
    BINOM[0].push_back (1);
    BINOM[1].push_back (1);
    BINOM[2].push_back (1);
    BINOM[2].push_back (2);
 
    for (int i = 3; i <= 20000; ++i)
    {
        BINOM[i].resize ( 1 + i / 2);
        BINOM[i][0] = 1;
        for (int j = 1; j + j < i; ++j)
            BINOM[i][j] = modulo (BINOM[i - 1][j] + BINOM[i - 1][j - 1]);
        if (i % 2 == 0) BINOM[i][i / 2] = modulo (2 * BINOM[i - 1][(i - 1) / 2]);
    }
}
 
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;
}