Grid Counting

Let’s translate the geometry into labels. For a black cell $(x,y)$ define

$$L=\max(x,y), \qquad R=\max(x,n+1-y).$$

The statement says every value $1,2,\dots,n$ appears exactly once as an $L$, and exactly once as an $R$.

Also, that immediately means there are exactly $n$ black cells. Therefore

$$\sum_{i=1}^{n} a_i = n$$

is mandatory. If not, answer is $0$. No cleverness can save it.

What cells in one row look like

Fix a row $x$.

If the cell is on the left side, meaning $y < x$, then

$$L=x, \qquad R=\max(x,n+1-y)>x.$$

If the cell is on the right side, meaning $y>n+1-x$, then

$$R=x, \qquad L=\max(x,y)>x.$$

For the middle interval, both $y\le x$ and $n+1-y\le x$, so both labels become

$$L=R=x.$$

That sounds scary, but it is mostly a trap. If the interval has length more than $1$, all those cells would have the same pair $(L,R)=(x,x)$, and choosing one would leave no way to distinguish columns by labels. More importantly, such cells only appear in lower rows, where smaller rows cannot later fix the already-burned labels cleanly. The only single “self-paired” cell that matters in the bottom-up count is the exact center when $n$ is odd:

$$mid = \frac{n+1}{2}, \qquad (mid,mid).$$

The useful consequence is:

• a row can contribute at most one cell using fixed $L=x$;
• a row can contribute at most one cell using fixed $R=x$;
• so $a_x$ can only be $0$, $1$, or $2$.

If any $a_x>2$, answer is $0$.

Process rows from bottom to top

Labels larger than $i$ can only be used by rows $\le i$. So process rows from $n$ down to $1$.

Keep two pools:

• unused $L$ labels greater than the current row;
• unused $R$ labels greater than the current row.

When row $i$ has:

• $a_i=0$: it uses neither fixed label $L=i$ nor fixed label $R=i$, so both labels become available for smaller rows.
• $a_i=1$: it places exactly one cell. Usually that means either fixed $L=i$ paired with an available larger $R$, or fixed $R=i$ paired with an available larger $L$.
• $a_i=2$: it places two cells, one of each kind.

The DP state

Let:

• eq = number of ways where both available pools have the same size;
• moreL = ways where the available $L$ pool has one extra label;
• moreR = ways where the available $R$ pool has one extra label.

Let small be the smaller pool size before processing the current row.

The imbalance never needs to exceed $1$ because each row can only affect the two current labels $L=i$ and $R=i$ in a very controlled way. If the input tries to demand nonsense, the transition count just becomes $0$.

Transitions

For row $i$:

If $a_i=0$, choose no cells. Both current labels become available, so the smaller pool size increases by $1$. The imbalance state stays the same.

If $a_i=1$:

• from eq, we can create moreL in small ways or moreR in small ways;
• from moreL, we can return to eq in small+1 ways;
• from moreR, symmetric, also small+1 ways;
• if $n$ is odd and $i=mid$, the center cell adds one extra way from eq to eq.

If $a_i=2$:

• from eq, choose one available $L$ and one available $R$: small * small;
• from moreL, choose among small+1 available $L$ and small available $R$;
• from moreR, symmetric;
• the smaller pool size decreases by $1$.

Why this counts grids

For fixed row $i$:

• choosing fixed $L=i$ and available $R=r$ uniquely determines a column on one side;
• choosing fixed $R=i$ and available $L=l$ uniquely determines a column on the other side;
• the exact odd center is one literal cell.

So every DP choice corresponds to real cells, and every valid grid produces exactly one sequence of DP choices. No double counting, no “trust me bro” geometry.

The answer is the balanced state after all rows are processed.

Time complexity is $O(n)$ per test case, with total $n\le 2\cdot 10^5$.