#include<bits/stdc++.h>
const int mod = 1e9 + 9;
using std::cin;
using std::cout;
using u64 = unsigned long long;
using ll = long long;
const int N = 500005;
int fac[N], ifac[N], inv[N];
int n;
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
	for(int i = 2;i < N;++i) {
		inv[i] = u64(mod - mod / i) * inv[mod % i] % mod;
		fac[i] = (u64) fac[i - 1] * i % mod;
		ifac[i] = (u64) ifac[i - 1] * inv[i] % mod;
	}
	int T; cin >> T;
	for(int i = 0;i < T;++i) {
		int n; cin >> n;
		std::vector<ll> a(n);

		ll sum = 0;
		for(int i = 0;i < n;++i) {
			cin >> a[i], a[i] *= 2;
			sum += a[i];
		}
		if(sum % n) {
			cout << 0 << '\n';
			continue;
		}
		sum /= n;
		sort(a.begin(), a.end());
		if(n % 2 == 1) {
			if(a[n / 2] != sum) {
				cout << 0 << '\n';
				continue;
			}
			a.erase(a.begin() + n / 2);
			-- n;
		}
		int ok = 1;
		for(int i = 0;i < n / 2;++i) {
			if(a[i] + a[n - 1 - i] != sum * 2) {
				ok = 0;
				break;
			}
		}
		if(!ok) {
			cout << 0 << '\n';
			continue;
		}
		std::vector<int> cnt;
		int cc = 0;
		for(int i = 0;i < n / 2;++i) {
			if(!i || a[i] != a[i - 1]) {
				cnt.push_back(cc);
				cc = 1;
			} else {
				++ cc;
			}
		}
		cnt.push_back(cc);
		int ans = fac[n / 2];
		for(int x : cnt) {
			ans = (u64) ans * ifac[x] % mod;
		}
		for(int i = 0;i < n / 2;++i) {
			if(a[i] != a[n - 1 - i])
				ans = ans * 2u % mod;
		}
		cout << ans << '\n';
	}
}