#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <assert.h>
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;

ll binpow(ll a, ll b){
    if(b == 0) return 1 % mod;
    ll ans = binpow(a, b / 2);
    ans = (ans * ans) % mod;
    if(b % 2 == 1) ans = (ans * a) % mod; 
    return ans % mod;
}
ll inverse(ll x){
    return binpow(x, mod - 2);
}


void solve(){
    ll n;
    cin >> n;

    vector<long long> a(n);
    map<long long, long long> m;
    vector<ll> v;

    ll ttl = 0;

    for(ll i = 0; i < n; i++){
        cin >> a[i];
        m[a[i]]++;
        ttl +=  a[i];
    }
    ll number;

    if(n % 2 == 1) number = n;
    else number = (n + 1) / 2;

    if(ttl % number != 0){
        cout << 0 << '\n';
        return;
    } 
    
    ll sum = ttl / number;
    if(n % 2 == 1) sum = sum * 2;

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

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