#include <bits/stdc++.h>

namespace IO {
	template <class Stream>
	Stream& fmtbase(Stream& out, const char* format) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				throw std::invalid_argument("Error Number of Parameters!");
			}
			
			out << *format;
		}
		
		return out;
	}
	
	template <class Stream, class Fst, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				out << value;
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}
	
	template <class... Ps>
	std::string to_string(const char* format, const Ps&... ps) {
		std::stringstream ss;
		fmtbase(ss, format, ps...);
		return ss.str();
	}

	template <class... Ps>
	std::ostream& fmtout(const char* format, const Ps&... ps) {
		return fmtbase(std::cout, format, ps...);
	}
	
	template <class... Ps>
	std::ostream& fmterr(const char* format, const Ps&... ps) {
		return fmtbase(std::cerr, format, ps...);
	}
	
	std::istream& allin() {
		return std::cin;
	}
	
	template <class Fst, class ... Nxt>
	std::istream& allin(Fst& fst, Nxt&... nxt) {
		std::cin >> fst;
		return allin(nxt...);
	}
	
	template <class Iter>
	std::istream& rangin(Iter begin, Iter end) {
		while (begin != end) {
			std::cin >> *begin;
			begin++;
		}
		
		return std::cin;
	}
	
	namespace Fast {
		bool sync = false;
		
		char buf[1 << 23];
		char *p1 = buf, *p2 = buf;
		
		void sync_with_ios(bool s) {
			sync = s;
		}
		
		char getchar() {
			if (sync) {
				return (char) std::cin.get();
			}
			else {
				if (p1 == p2) {
					p1 = buf;
					p2 = p1 + fread(buf, 1, 1 << 22, stdin);
				}
				
				if (p1 == p2) {
					return EOF;
				}
				else {
					char res = *p1;
					p1++;
					return res;
				}
			}
		}
		
		void read() { }
		
		template <class T, class... U>
		void read(T& x, U&... us) {
			x = 0;
			T pos = 1;
			
			char c = getchar();
			while (!isdigit(c)) {
				if (c == '-') {
					pos = -1;
				}
				
				c = getchar();
			}
			
			while (isdigit(c)) {
				x = 10 * x + c - '0';
				c = getchar();
			}
			
			x *= pos;
			read(us...);
		}
		
		template <class T>
		void write(const T& t) {
			if (t > 10) {
				write(t / 10);
			}
			
			std::cout << (int) (t % 10);
		}
	}
}

namespace Solve {
	#define int long long

	using namespace IO;

	using ll = long long;
	using ul = unsigned long long;
	using db = double;
	using ld = long double;
	using ui = unsigned int;
	using ib = __int128;
	using ub = __uint128_t;

	int const INF = std::numeric_limits<int>::max();
	int const NINF = std::numeric_limits<int>::min();
	ll const LINF = std::numeric_limits<ll>::max();
	ll const LNINF = std::numeric_limits<ll>::min();
	ld const EPS = 1e-6;

	template <class T>
	inline int isz(const T& v) {
		return v.size();
	}

	template <class T>
	inline T& ckmx(T& a, T b) {
		return a < b ? (a = b) : a;
	}

	template <class T>
	inline T& ckmi(T& a, T b) {
		return a > b ? (a = b) : a;
	}

	template <int M>
	struct ModInt {
		static int const MOD = M;
		
		int v;
		
		ModInt() : v(0) { }
		
		ModInt(long long v) {
			if (-MOD <= v && v < 2 * MOD) {
				if (v >= MOD) {
					v -= MOD;
				}
				else if (v < 0) {
					v += MOD;
				}
			}
			else {
				v %= MOD;
				if (v < 0) {
					v += MOD;
				}
			}
			
			this->v = v;
		}
			
		ModInt operator++(signed) {
			auto t = *this;
			operator+=(1);
			return t;
		}
		
		ModInt& operator++() {
			operator+=(1);
			return *this;
		}
		
		ModInt operator--(signed) {
			auto t = *this;
			operator-=(1);
			return t;
		}
		
		ModInt& operator--() {
			operator-=(1);
			return *this;
		}
		
		ModInt& operator+=(const ModInt& rhs) {
			v = v + rhs.v >= MOD ? v + rhs.v - MOD : v + rhs.v;
			return *this;
		}
		
		friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) {
			ModInt res = lhs;
			res += rhs;
			
			return res;
		}
		
		ModInt& operator-=(const ModInt& rhs) {
			v = v - rhs.v < 0 ? v - rhs.v + MOD : v - rhs.v;
			return *this;
		}
		
		friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) {
			ModInt res = lhs;
			res -= rhs;
			
			return res;
		}
		
		ModInt& operator*=(const ModInt& rhs) {
			v = 1ll * v * rhs.v % MOD;
			return *this;
		}
		
		friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) {
			ModInt res = lhs;
			res *= rhs;
			
			return res;
		}
		
		ModInt fpow(long long p) const {
			if (p < 0) {
				return fpow(-p).inv();
			}
			else if (!p) {
				return 1;
			}
			else if (p == 1) {
				return *this;
			}
			else if (p == 2) {
				return *this * *this;
			}
			else {
				return fpow(p / 2).fpow(2) * fpow(p % 2);
			}
		}
		
		friend bool operator==(const ModInt& a, const ModInt& b) {
			return a.v == b.v;
		}
		
		friend bool operator!=(const ModInt& a, const ModInt& b) {
			return a.v != b.v;
		}
		
		friend ModInt operator-(const ModInt& a) {
			ModInt res;
			if (a.v == 0) {
				return 0;
			}
			
			res.v = MOD - a.v;
			return res;
		}
		
		ModInt inv() const {
			return fpow(MOD - 2);
		}
		
		ModInt operator/=(const ModInt& rhs) {
			// O(log MOD)
			return operator*=(rhs.inv());
		}
		
		friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) {
			ModInt res = lhs;
			res /= rhs;
			
			return res;
		}
		
		bool is_square() const {
			return v == 0 || fpow((MOD - 1) / 2).v == 1;
		}
		
		ModInt sqrt() const {
			static std::mt19937 mt(42334435);
			static ModInt isq;
			
			assert(is_square());
			
			struct Complex {
				ModInt a, b;
				
				Complex operator*(const Complex& rhs) const {
					return { a * rhs.a + isq * b * rhs.b, a * rhs.b + b * rhs.a };
				}
				
				Complex fpow(int n) {
					if (!n) {
						return { 1, 0 };
					}
					else if (n == 1) {
						return *this;
					}
					else if (n == 2) {
						return operator*(*this);
					}
					else {
						return fpow(n / 2).fpow(2) * fpow(n % 2);
					}
				}
			};
			
			if (v == 0) {
				return 0;
			}
			
			ModInt b;
			while (true) {
				b = mt() % MOD;
				if (!(b * b - *this).is_square()) {
					break;
				}
			}
			
			isq = b * b - *this;
			
			Complex c = { b, 1 };
			auto res = c.fpow((MOD + 1) / 2).a;
			return std::min(res.v, MOD - res.v);
		}
	};
	
	template <int MOD>
	std::istream& operator>>(std::istream& in, ModInt<MOD>& mint) {
		long long v;
		in >> v;
		mint = ModInt<MOD>(v);
		
		return in;
	}
	
	template <int MOD>
	std::ostream& operator<<(std::ostream& out, const ModInt<MOD>& mint) {
		return out << mint.v;
	}
	
	template <class T, int B>
	struct FastPow {
		T baby[B + 1];
		T gaint[B + 1];
		
		FastPow(T b) {
			baby[0] = 1;
			for (int i = 1; i <= B; i++) {
				baby[i] = baby[i - 1] * b;
			}
			
			gaint[0] = 1;
			for (int i = 1; i <= B; i++) {
				gaint[i] = gaint[i - 1] * baby[B];
			}
		}
		
		T get(int n) {
			return gaint[n / B] * baby[n % B];
		}
	};
	
	int const MOD = 1e9 + 7;
	
	template <int M>
	const int ModInt<M>::MOD;
	
	using Mint = ModInt<MOD>;
	
	int const K = 10;
	int const M = 3010;

	Mint f[M + 1][1 << K];
	int n, m, k;

	void main() {
		std::cin >> n >> m >> k;
		for (int i = 2; i <= n; i++) {
			int f;
			std::cin >> f;
		}

		f[0][0] = 1;
		for (int i = 0; i < m; i++) {
			for (int s = 0; s < (1 << k); s++) {
				if (f[i][s] == 0) {
					continue;
				}

				if (s & 1) {
					f[i + 1][s >> 1] += f[i][s];
				}
				else {
					int c = n + i + __builtin_popcount(s);
					f[i + 1][s >> 1] += f[i][s] * (2 * c - 1);
					int ns = s >> 1;
					for (int j = 0; j < k; j++) {
						if (!((ns >> j) & 1)) {
							f[i + 1][ns | (1 << j)] += f[i][s] * (c - 1);
						}
					}
				}
			}
		}

		fmtout("{}\n", f[m][0]);
	}

	void init() {

	}

	void clear() {
		for (int i = 0; i <= m; i++) {
			for (int s = 0; s < (1 << k); s++) {
				f[i][s] = 0;
			}
		}

		n = m = k = 0;
	}
}

signed main() {
#ifndef ONLINE_JUDGE
	auto input_file = freopen("d.in", "r", stdin);
	auto output_file = freopen("d.out", "w", stdout);
#endif
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int t = 1;
	std::cin >> t >> t;

	Solve::init();
	
	for (int id = 1; id <= t; id++) {
		Solve::main();
		Solve::clear();
	}

#ifndef ONLINE_JUDGE
	std::cout.flush();
	fclose(input_file);
	fclose(output_file);
#endif
	
	return 0;
}