极限超频竞技AC版

// 极限超频（但逻辑正确）版本：fast IO + O(N^2) pre + O(E*O) rolling DP
// 编译建议：g++ -O2 -march=native -pipe -static -s -std=gnu++17 fast_counting.cpp

#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;
static const int MOD = 1000000007;
static const int MAXN = 5005;

// ---------- fast fread/fwrite I/O ----------
static const int BUFSIZE = 1 << 20;
static char ibuf[BUFSIZE];
static int ipos = 0, ilen = 0;
static inline char nextChar() {
if (ipos >= ilen) {
ilen = (int)fread(ibuf, 1, BUFSIZE, stdin);
ipos = 0;
if (ilen == 0) return EOF;
}
return ibuf[ipos++];
}
static inline void readInt(int &out) {
char c; int sign = 1; int x = 0;
do { c = nextChar(); if (c == EOF) { out = 0; return; } } while (c <= ' ');
if (c == '-') { sign = -1; c = nextChar(); }
for (; c > ' '; c = nextChar()) x = x * 10 + (c - '0');
out = x * sign;
}

static char obuf[BUFSIZE];
static int opos = 0;
static inline void flushOut() {
if (opos) {
fwrite(obuf, 1, opos, stdout);
opos = 0;
}
}
static inline void writeChar(char c) {
if (opos >= BUFSIZE) flushOut();
obuf[opos++] = c;
}
static inline void writeIntLn(int x) {
if (x == 0) {
writeChar('0'); writeChar('\n'); return;
}
if (x < 0) { writeChar('-'); x = -x; }
char s[16]; int n = 0;
while (x) { s[n++] = char('0' + (x % 10)); x /= 10; }
while (n--) writeChar(s[n]);
writeChar('\n');
}
// ---------- end IO ----------

// Global arrays (to avoid dynamic alloc overhead)
static int a[MAXN];
static int q0[MAXN], q1[MAXN]; // indices (1-based original index)
static int cnt0, cnt1;
static int posInParity[MAXN]; // posInParity[orig_index] -> 0-based rank inside its parity group
static int preArr[MAXN]; // pre per original index

// dp rolling arrays
static int dp[MAXN], nxt[MAXN];

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
readInt(T);
while (T--) {
    int n;
    readInt(n);
    // read array (1-based index used for convenience)
    for (int i = 1; i <= n; ++i) {
        readInt(a[i]);
    }

    // build parity lists (keep original indices)
    cnt0 = cnt1 = 0;
    for (int i = 1; i <= n; ++i) {
        if ((a[i] & 1) == 0) {
            q0[++cnt0] = i;
            posInParity[i] = cnt0 - 1; // 0-based position among evens
        } else {
            q1[++cnt1] = i;
            posInParity[i] = cnt1 - 1; // 0-based position among odds
        }
    }

    // initialize pre to max (means no blocker)
    for (int i = 1; i <= n; ++i) {
        preArr[i] = ((a[i] & 1) ? cnt0 : cnt1); // if odd -> pre default = number of evens; if even -> pre = number of odds
    }

    // compute pre: for each i, scan j>i; if parity different AND |a[i]-a[j]|>1, update pre[i] = min(pre[i], posInParity[j])
    // micro-optimizations: local pointers, simple arithmetic, avoid abs call
    for (int i = 1; i <= n; ++i) {
        int ai = a[i];
        int &pre_i = preArr[i];
        // scan j > i
        for (int j = i + 1; j <= n; ++j) {
            int aj = a[j];
            // check parity difference quickly by (ai - aj) & 1
            int diff = ai - aj;
            // if parity equal -> diff is even -> lower bit 0
            if ((diff & 1) == 0) continue; // same parity, cannot block by value differential (their diff even, so not >1 odd)
            // if absolute diff <= 1 then not blocker
            if (diff <= 1 && diff >= -1) continue;
            // blocker: j is opposite parity and abs(diff) > 1
            int pj = posInParity[j];
            if (pj < pre_i) pre_i = pj;
            // once pre_i == 0 we cannot get smaller, can break early
            if (pre_i == 0) break;
        }
        // note: if pre_i initially equals group size, it stays as group size (meaning no blocker)
    }

    // DP rolling: dp[j] = number of ways when used i evens and j odds (we iterate i from 0..cnt0)
    // initialize dp for i=0: only dp[0]=1
    for (int j = 0; j <= cnt1; ++j) dp[j] = 0;
    dp[0] = 1;

    for (int i = 0; i <= cnt0; ++i) {
        // Stage 1: allow placing more odds while staying at same i (i evens fixed)
        // We try transitions (i, j) -> (i, j+1)
        // We iterate j from 0..cnt1-1
        for (int j = 0; j < cnt1; ++j) {
            int cur = dp[j];
            if (!cur) continue;
            // index in original array of next odd to place is q1[j+1]
            int idx_next_odd = q1[j+1];
            bool ok;
            if (i == 0) {
                ok = true;
            } else {
                int idx_last_even = q0[i]; // the i-th even placed (1-based in q0)
                if (idx_last_even < idx_next_odd) ok = true;
                else {
                    // need to check whether idx_next_odd can cross idx_last_even
                    // That requires checking whether idx_next_odd is blocked by idx_last_even in original pre logic
                    // p equivalent: idx_next_odd can move past idx_last_even iff there is no blocker between them that forbids it
                    // The correct condition in our model is: posInParity[idx_next_odd]'s value <= preArr[idx_last_even]
                    // But careful: earlier derivation uses pre on each element: when placing odd j+1 after i evens, we must ensure
                    // i <= preArr[idx_next_odd]. However this check is equivalent to when we place odd after evens.
                    // For the transition (i, j)->(i, j+1), we must ensure i <= preArr[idx_next_odd].
                    // So use that condition (faster and correct).
                    ok = (i <= preArr[idx_next_odd]);
                }
            }
            if (ok) {
                int &dest = dp[j+1];
                dest += cur;
                if (dest >= MOD) dest -= MOD;
            }
        }

        // If we've placed all evens already, no need to prepare next row
        if (i == cnt0) break;

        // Stage 2: prepare nxt for placing next even (i+1)
        for (int j = 0; j <= cnt1; ++j) nxt[j] = 0;

        int idx_next_even = q0[i+1];
        for (int j = 0; j <= cnt1; ++j) {
            int cur = dp[j];
            if (!cur) continue;
            bool ok;
            if (j == 0) ok = true;
            else {
                int idx_last_odd = q1[j]; // last odd placed
                if (idx_last_odd < idx_next_even) ok = true;
                else {
                    // For placing even after j odds, we must ensure j <= preArr[idx_next_even]
                    ok = (j <= preArr[idx_next_even]);
                }
            }
            if (ok) {
                int &d = nxt[j];
                d += cur;
                if (d >= MOD) d -= MOD;
            }
        }

        // move nxt -> dp (rolling)
        for (int j = 0; j <= cnt1; ++j) dp[j] = nxt[j];
    }

    int answer = dp[cnt1];
    writeIntLn(answer);
}

flushOut();
return 0;

}