#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;

const long long N = 2e5 + 5, mod = 1e9 + 9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll inverse(ll a){
    return binpow(a, mod - 2, mod);
}


void solve(){
    int n;
    cin >> n;
    map<ll, ll> m;
    ll ttl = 0;

    for(int i = 0; i < n; i++){
        ll input;
        cin >> input;
        ttl += input;
        m[input]++;
    }   
    if((n % 2 == 1 && ttl % n != 0) || (n % 2 == 0 && ttl % (n / 2) != 0)){
        cout << 0 << '\n';
        return;
    }
    ll sum = ttl * 2 / n;
    
    if(n % 2 == 1 && sum % 2 == 1){
        cout << 0 << '\n';
        return;
    }
    if(n % 2 == 1 && m.find(sum / 2) == m.end()){
        cout << 0 << '\n';
        return;
    }
    if(n % 2 == 1) m[sum / 2]--;

    vector<ll> v;
    ll pow_2 = 0;

    for(auto& x : m){
        if(x.ff > sum / 2) continue;
        
        if(sum % 2 == 0 && x.ff == sum / 2 && x.ss % 2 == 1){
            cout << 0 << '\n';
            return;
        }
        
        if(sum % 2 == 0 && x.ff == sum / 2){
            v.pb(x.ss / 2);
            continue;
        }
        if(m.find(sum - x.ff) == m.end() || m[sum - x.ff] != x.ss){
            cout << 0 << '\n';
            return;
        } 
        v.pb(x.ss);
        pow_2 += x.ss;
    }
    vector<ll> fac(n);
    fac[0] = 1;
    fac[1] = 1;
    for(ll i = 2; i < n; i++){
        fac[i] = (fac[i - 1] * i) % mod; 
    }
    ll ans = fac[n / 2];
    for(auto& x : v){   
        ans = (ans * inverse(fac[x])) % mod; 
    }
    ans = (ans * binpow(2, pow_2, mod)) % mod;
    cout << ans << '\n';
    return;
}

int main(){
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}