#include <bits/stdc++.h>

using namespace std;

const int N = 3.3e4 + 10, K = 10, MOD = 1e9 + 7;

int dp[N][1 << K], n, m, k;

void solve()
{
	cin >> n >> m >> k;
	for (int i = 1, x; i <= n - 1; i++) cin >> x;
	
	for (int i = n; i <= n + m; i++) memset(dp[i], 0, sizeof dp[i]);
	dp[n][0] = 1;
	for (int i = n; i < n + m; i++)
		for (int j = 0; j < (1 << k); j++)
			if (j & 1) (dp[i + 1][j >> 1] += dp[i][j]) %= MOD;
			else
			{
				int s = __builtin_popcount(j);
				(dp[i + 1][j >> 1] += 1ll * dp[i][j] * ((i + s) + (i + s - 1))) %= MOD;
				for (int p = 0; p < k && i + 1 + p <= n + m; p++) 
					if (!((j >> 1) & (1 << p))) (dp[i + 1][(j >> 1) | (1 << p)] += 1ll * dp[i][j] * (i + s - 1)) %= MOD;
			}
	cout << dp[n + m][0] << '\n';
}

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	
	int c, t; cin >> c >> t;
	while (t--) solve();	
}