CodeChef submission 136642 (C++ 4.0.0-8) plaintext list. Status: AC, problem SNCK03, contest SNACKDWN. By gri (gri), 2009-11-21 23:39:31.
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
#include "float.h"
using namespace std;
 
#define FOR(i, a, b) for (int i(a), _b(b); i <= _b; ++i)
#define FORD(i, a, b) for (int i(a), _b(b); i >= _b; --i)
#define REP(i, n) for (int i(0), _n(n); i < _n; ++i)
#define REPD(i, n) for (int i((n)-1); i >= 0; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long int64;
typedef unsigned long long uint64;
 
template<typename T> int size(const T& c) { return (int)c.size(); }
template<typename T> void remin(T& a, const T& b) { if (b < a) a = b; }
template<typename T> void remax(T& a, const T& b) { if (b > a) a = b; }
template<typename T> T abs(T x) { return x < 0 ? -x : x; }
template<typename T> T sqr(T x) { return x*x; }
 
const int mod = 1000000007;
 
inline int mult(int a, int b) {
	return int(int64(a)*b%mod);
}
 
inline int add(int a, int b) {
	int res = a+b;
	if (res >= mod) res -= mod;
	return res;
}
 
int power(int a, int n) {
	a = (a%mod+mod)%mod;
	if (a == 0) return 0;
	int res = 1;
	while (n > 0) {
		if (n&1)
			res = mult(res, a);
		n >>= 1;
		a = mult(a, a);
	}
	return res;
}
 
int factorial(int n) {
	assert(n >= 0);
	static vector<int> memo;
	while (int(memo.size()) <= n) {
		if (memo.empty())
			memo.push_back(1);
		else 
			memo.push_back(mult(int(memo.size()), memo.back()));
	}
	return memo[n];
}
 
int inverse(int x) {
	return power(x, mod-2);
}
 
int inverseFactorial(int n) {
	assert(n >= 0);
	static vector<int> memo;
	while (int(memo.size()) <= n) {
		if (memo.empty()) 
			memo.push_back(1);
		else 
			memo.push_back(mult(inverse(int(memo.size())), memo.back()));
	}
	return memo[n];
}
 
int choose(int n, int m) {
	assert(n >= 0);
	if (m < 0 || m > n)
		return 0;
	int res = mult(factorial(n), mult(inverseFactorial(m), inverseFactorial(n-m)));
	return res;
}
 
int bruteForceDP(int first, int* a, int n) {
	vector<int> A;
	A.push_back(0);
	REP(i, n)
		A.push_back(a[i]-first);
	n = size(A);
	assert(n >= 2);
	REP(i, n-1)
		assert(A[i] < A[i+1]);
	int res = 0;
	vector<int> perm(A.back()+1);
	REP(i, size(perm))
		perm[i] = i;
	do {
		bool ok = perm[0] == 0;
		if (size(A)%2 == 0)
			ok = ok && perm.back() == size(perm)-1;
		else
			ok = ok && perm.back() == 1;
		REP(i, n-1) FOR(j, A[i], A[i+1]-1)
			if (i%2 == 0 && perm[j] > perm[j+1] || i%2 == 1 && perm[j] < perm[j+1]) {
				ok = false;
				break;
			}
		if (ok) 
			++res;
	} while (next_permutation(ALL(perm)));
	return res;
}
 
const int maxn = 20000;
const int maxk = 22;
int n, k;
 
int a[maxk];
int dp[maxk][maxk][maxn];
int dp2[maxk][maxk][2][2];
 
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "rt", stdin);
	//freopen("output.txt", "wt", stdout);
#endif
 
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &k);
		REP(i, k) {
			scanf("%d", &a[i]);
			--a[i];
		}
		REP(i, k) dp[i][i][a[i]] = 1;
		FOR(delta, 1, k-1) for (int i = 0, j = delta; j < k; ++i, ++j)
		FORD(p, a[i+1]-1, a[i]) {
			if (i == 1 && j == 4 && p == 3) {
				bool breakpoint = true;
			}
			if (j-i == 1) {
				dp[i][j][p] = 1;
			} else if (j-i == 2) {
				dp[i][j][p] = choose(a[j]-p-2, a[i+1]-p-1);
			} else if ((j-i)%2 == 1) {
				dp[i][j][p] = p+1 < a[i+1] ? dp[i][j][p+1] : 0;
				for (int q = i+2; q < j; q += 2) {
					int cur = mult(dp[i][q][p], dp[q][j][a[q]]);
					cur = mult(cur, choose(a[j]-p-2, a[q]-p-1));
					dp[i][j][p] = add(dp[i][j][p], cur);
				}
			} else {
				dp[i][j][p] = 0;
				for (int q = i+1; q < j; q += 2) {
					int cur = mult(dp[i][q][p], dp[q][j][a[q]]);
					cur = mult(cur, choose(a[j]-p-2, a[q]-p-1));
					dp[i][j][p] = add(dp[i][j][p], cur);
				}
			}
			//int bf = bruteForceDP(p, a+(i+1), j-i);
			//if (bf != dp[i][j][p]) 
			//	assert(false);
		}
		REP(i, k) REP(fi, 2) REP(fj, 2)
			dp2[i][i][fi][fj] = 1;
		FOR(delta, 1, k-1) 
			for (int i = 0, j = delta; j < k; ++i, ++j) 
				REPD(fi, 2) REPD(fj, 2) { 					
					int& res = dp2[i][j][fi][fj];
					res = 0;
					if (i == 0 && j == 3 && fi == 0 && fj == 0)
						res = 0;
					if (fi == 1 && fj == 1)
						res = dp[i][j][a[i]];
					else if (j-i == 1)
						res = 1;
					else if (j-i == 2)
						res = choose(a[j]-a[i]-fi-fj, a[i+1]-a[i]-fi);
					else if ((j-i)%2 == 0) {
						for (int q = i+1; q < j; q += 2) {
							int cur = mult(dp2[i][q][fi][1], dp2[q][j][1][fj]);
							cur = mult(cur, choose(a[j]-a[i]-fi-fj, a[q]-a[i]-fi));
							res = add(res, cur);
						}
					} else {
						if (fi == 0) {
							for (int q = i; q < j; q += 2) {
								int cur = mult(dp2[i][q][fi][1], dp2[q][j][1][fj]);
								cur = mult(cur, choose(a[j]-a[i]-fi-fj, a[q]-a[i]-fi));
								res = add(res, cur);
							}
						} else {
							for (int q = j; q > i; q -= 2) {
								int cur = mult(dp2[i][q][fi][1], dp2[q][j][1][fj]);
								cur = mult(cur, choose(a[j]-a[i]-fi-fj, a[q]-a[i]-fi));
								res = add(res, cur);
							}
						}
					}
				}
		printf("%d\n", dp2[0][k-1][0][0]);
	}
 
	exit(0);
}