#include <bits/stdc++.h>

#define ll long long

const ll MM = 1e9 + 9, N = 5e5 + 10;

using namespace std;

ll pow(ll a, ll b, ll m) {
	ll res = 1;
	while (b) {
		if (b % 2) {
			res = res * a % m;
		}
		a = a * a % m;
		b /= 2;
	}
	return res;
}
ll inverse_mod(ll a, ll m) {
	return pow(a, m - 2, m);
}



ll fact[N];

ll Com(ll n, ll r) {
	return fact[n] * inverse_mod(fact[r] * fact[n - r] % MM, MM) % MM;
}

void factt() {
	fact[0] = 1;
	for (ll i = 1; i < N; i++) {
		fact[i] = fact[i - 1] * i % MM;
	}
}

int solve() {
	int n; cin >> n;
	vector<ll>v(n);
	ll sum = 0;
	map<ll, ll>mp;
	for (auto& x : v) {
		cin >> x;
		sum += x;
		mp[x]++;
	}
	if ((sum * 2) % (n))return cout << 0 << '\n', 0;

	ll d = sum * 2 / n;

	if (n % 2) {
		if (d % 2)return cout << 0 << '\n', 0;
		if (mp[d / 2] % 2 == 0)return cout << 0 << '\n', 0;
		mp[d / 2]--;
		if (!mp[d / 2])mp.erase(d / 2);
		n--;
	}

	ll res = pow(2, n / 2, MM) * fact[n / 2] % MM;
	vector<ll>vv;
	n /= 2;
	for (auto x : mp) {
		if (x.first + x.first == d) {
			if (x.second % 2)return cout << 0 << '\n', 0;
			res *= inverse_mod(x.second / 2, MM);
			res %= MM;
			res *= inverse_mod(pow(2, x.second / 2, MM), MM);
			res %= MM;
			n -= x.second / 2;
			continue;
		}
		if (mp[d - x.first] != x.second) {
			return cout << 0 << '\n', 0;
		}
		vv.emplace_back(x.second);
		mp.erase(d - x.first);
	}
	for (auto x : vv) {
		res *= inverse_mod(fact[x], MM);
		res %= MM;
	}

	cout << res << '\n';



	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	factt();
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}