#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
const int mod = int(1e9 + 7);
int n, m, k;
int f[1 << 10], g[1 << 10];
int bit[1 << 10];
void add(int &x, int y) {x = (x + y >= mod ? x + y - mod : x + y);}
void sol()
{
	n = read(), m = read(), k = read();
	FOR(i, 1, n - 1) {int x = read();}
	if (k == 0)
	{
		int ans = 1;
		FOR(i, n, n + m - 1)ans = 1LL * ans * (2 * i - 1) % mod;
		cout << ans << '\n'; return ;
	}
	FOR(i, 0, (1 << k) - 1)f[i] = 0; f[0] = 1;
	FOR(i, n, n + m - 1)
	{
		FOR(S, (1 << k - 1), (1 << k) - 1)add(g[(S << 1) & ((1 << k) - 1)], f[S]);
		FOR(S, 0, (1 << k - 1) - 1)
		{
			FOR(j, 0, k - 2)if ((S >> j) & 1)add(g[(S ^ (1 << j)) << 1], f[S]);
			add(g[S << 1], 1LL * f[S] * (2LL * (i + bit[S]) - 1) % mod);
			add(g[S << 1 | 1], 1LL * f[S] * (i + bit[S] - 1) % mod);
		}
		FOR(S, 0, (1 << k) - 1)f[S] = g[S], g[S] = 0;
	}
	cout << f[0] << '\n';
}
int main()
{
	// freopen("tree.in", "r", stdin);
	// freopen("tree.out", "w", stdout);
	FOR(i, 0, (1 << 10) - 1)bit[i] = bit[i >> 1] + (i & 1);
	int k = read(); int T = read();
	while (T --)sol();
	return 0;
}