long mod = 1000000007;

long beautifulPermutations(int n, vector<long>& A) {
    sort(A.begin(), A.end());
    long once = 0, twice = 0, inverse = 1;
    for (int i = 0; i < n-1; i++) if (A[i] == A[i+1]) twice++;
    once = n - 2 * twice;
    for (int i = 1; i <= twice; i++) inverse = (inverse * 500000004) % mod;
    vector<vector<long>> cache(twice+1, vector<long>(n + 1));
    cache[0][0] = 1;
    for (int i=1; i <= once; i++) cache[0][i] = (cache[0][i-1] * (once - i + 1)) % mod;
    for (int i = 1; i <= twice; i++) {
        cache[i][0] = 1;
        cache[i][1] = once + 2*i;
        for (int L = 1; L < once + 2 * i; L++) {
            long G = (cache[i - 1][L - 1] * i * 2) % mod;
            long H = (cache[i][L] - G) % mod;
            cache[i][L + 1] = (G * (once + 2*i - 1 - L) + H * (once + 2*i - L)) % mod;
        }
    }
    return ((cache[twice][n] + mod) * inverse) % mod;
}