TNFSHOJ 564

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) (int)(X).size()

void extgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
    }else{
        extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }
}

int moni(int k, int mod){
    int x,y;
    extgcd(k, mod, x, y);
    return (x%mod+mod) % mod;
}

const int M = 1e9+7;
int form[1000001];
int arr[1000001];
int cnt[1000001];
int n;

struct XD{
    int idx,val,cur;
}aux[1000001];
bool cmp1(XD a, XD b){return a.val < b.val;}
bool cmp2(XD a, XD b){return a.idx < b.idx;}

void discretize(){
    for(int i = 0; i < n; ++i){
        aux[i] = {.idx = i, .val = arr[i], .cur = 1};
    }
    sort(aux, aux+n, cmp1);
    for(int i = 1; i < n; ++i){
        if(aux[i].val == aux[i-1].val){
            aux[i].cur = aux[i-1].cur;
        }else{
            aux[i].cur = aux[i-1].cur + 1;
        }
    }
    sort(aux, aux+n, cmp2);
    for(int i = 0; i < n; ++i){
        arr[i] = aux[i].cur;
    }
}

int32_t main(){
    cin >> n;
    for(int i = 0; i < n; ++i)cin >> arr[i];
    discretize();
    form[0] = 1;
    for(int i = 1; i <= n; ++i)form[i] = form[i-1] * i % M;
    int bnd = 1;
    for(int i = 0; i < n; ++i){
        bnd = max(bnd, arr[i]);
        ++cnt[arr[i]];
    }
    bool yes = 1;
    int odd = 0;
    int ans = 1;
    if(n & 1){
        for(int i = 1; i <= bnd && yes; ++i){
            if((cnt[i] & 1) && odd != 0)yes = 0;
            else if(cnt[i] & 1)odd = i;
        }
    }else{
        for(int i = 1; i <= bnd && yes; ++i){
            if(cnt[i] & 1)yes = 0;
        }
    }
    //cout << yes << '\n';
    if(yes){
        for(int i = 1; i <= bnd; ++i){
            ans = ans * form[cnt[i]] % M;
            ans = ans * moni(form[cnt[i]/2], M) % M;
        }
        ans = ans * (form[n/2]) % M;
        cout << ans << '\n';
    }else{
        cout << 0 << '\n';
    }
    return 0;
}