Permutation Blackhole

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const int MOD = 998244353;

struct State2 {
    int a, b, ways;
};

struct State1 {
    int a, ways;
};

int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int mulmod(ll a, ll b) {
    return int(a * b % MOD);
}

int main() {
    setIO();

    const int MAXN = 105;
    vector<vector<int>> comb(MAXN, vector<int>(MAXN));
    for (int i = 0; i < MAXN; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            comb[i][j] = addmod(comb[i - 1][j - 1], comb[i - 1][j]);
        }
    }

    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++) cin >> s[i];

        vector<vector<vector<State2>>> both(n + 2, vector<vector<State2>>(n + 2));
        vector<vector<vector<State1>>> onlyR(n + 2, vector<vector<State1>>(n + 2));
        vector<vector<vector<State1>>> onlyL(n + 2, vector<vector<State1>>(n + 2));

        int acc2[MAXN][MAXN] = {};
        int seen2[MAXN][MAXN] = {};
        int acc1[MAXN] = {};
        int seen1[MAXN] = {};
        int stamp2 = 0, stamp1 = 0;

        auto add2 = [&](vector<pair<int, int>>& touched, int a, int b, int val) {
            if (seen2[a][b] != stamp2) {
                seen2[a][b] = stamp2;
                acc2[a][b] = 0;
                touched.push_back({a, b});
            }
            acc2[a][b] = addmod(acc2[a][b], val);
        };

        auto add1 = [&](vector<int>& touched, int a, int val) {
            if (seen1[a] != stamp1) {
                seen1[a] = stamp1;
                acc1[a] = 0;
                touched.push_back(a);
            }
            acc1[a] = addmod(acc1[a], val);
        };

        for (int len = 1; len <= n - 1; len++) {
            for (int L = 1; L + len <= n; L++) {
                int R = L + len;
                if (len == 1) {
                    both[L][R].push_back({0, 0, 1});
                    continue;
                }

                ++stamp2;
                vector<pair<int, int>> touched;

                for (int x = L + 1; x <= R - 1; x++) {
                    int leftCnt = x - L - 1;
                    int rightCnt = R - x - 1;
                    int mergeWays = comb[leftCnt + rightCnt][leftCnt];
                    int addL = (x - L <= R - x);
                    int addR = 1 - addL;

                    for (const auto& A : both[L][x]) {
                        for (const auto& B : both[x][R]) {
                            if (s[x] != -1 && A.b + B.a != s[x]) continue;
                            int ways = mulmod(mulmod(A.ways, B.ways), mergeWays);
                            add2(touched, A.a + addL, B.b + addR, ways);
                        }
                    }
                }

                for (auto [a, b] : touched) {
                    if (acc2[a][b]) both[L][R].push_back({a, b, acc2[a][b]});
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            onlyR[i][i].push_back({0, 1});
            onlyL[i][i].push_back({0, 1});
        }

        for (int len = 1; len <= n - 1; len++) {
            for (int R = 1; R <= n; R++) {
                int L = R - len;
                if (L < 1) continue;

                ++stamp1;
                vector<int> touched;

                for (int x = L; x <= R - 1; x++) {
                    int leftCnt = x - L;
                    int rightCnt = R - x - 1;
                    int mergeWays = comb[leftCnt + rightCnt][leftCnt];

                    for (const auto& A : onlyR[L][x]) {
                        for (const auto& B : both[x][R]) {
                            if (s[x] != -1 && A.a + B.a != s[x]) continue;
                            int ways = mulmod(mulmod(A.ways, B.ways), mergeWays);
                            add1(touched, B.b + 1, ways);
                        }
                    }
                }

                for (int a : touched) {
                    if (acc1[a]) onlyR[L][R].push_back({a, acc1[a]});
                }
            }

            for (int L = 1; L <= n; L++) {
                int R = L + len;
                if (R > n) continue;

                ++stamp1;
                vector<int> touched;

                for (int x = L + 1; x <= R; x++) {
                    int leftCnt = x - L - 1;
                    int rightCnt = R - x;
                    int mergeWays = comb[leftCnt + rightCnt][leftCnt];

                    for (const auto& A : both[L][x]) {
                        for (const auto& B : onlyL[x][R]) {
                            if (s[x] != -1 && A.b + B.a != s[x]) continue;
                            int ways = mulmod(mulmod(A.ways, B.ways), mergeWays);
                            add1(touched, A.a + 1, ways);
                        }
                    }
                }

                for (int a : touched) {
                    if (acc1[a]) onlyL[L][R].push_back({a, acc1[a]});
                }
            }
        }

        int ans = 0;
        for (int r = 1; r <= n; r++) {
            int mergeWays = comb[n - 1][r - 1];
            for (const auto& L : onlyR[1][r]) {
                for (const auto& R : onlyL[r][n]) {
                    if (s[r] != -1 && L.a + R.a != s[r]) continue;
                    int ways = mulmod(mulmod(L.ways, R.ways), mergeWays);
                    ans = addmod(ans, ways);
                }
            }
        }

        cout << ans << '\n';
    }
}