Catwalk BrainF**k

Suppose exactly $2k$ bracket characters appear. Their positions can be chosen in $\binom{N}{2k}$ ways, and each remaining position can contain any of the six non-bracket characters. The number of correct bracket strings on the chosen $2k$ positions is the Catalan number

$$\mathrm{Cat}(k)=\frac{1}{k+1}\binom{2k}{k}.$$

Therefore, if $A_N$ is the number of compilable strings of length $N$,

$$A_N=\sum_{k=0}^{\lfloor N/2\rfloor}\binom{N}{2k}\mathrm{Cat}(k)6^{N-2k}.$$

For a single test case, evaluating this sum directly gives an $O(N)$ solution.

To handle all test cases efficiently, precompute every $A_N$ in linear time. Interpret [ as a step that increases the height by $1$, ] as a step that decreases the height by $1$, and each of the other six characters as a distinct step that keeps the height unchanged. A compilable string is exactly a weighted Motzkin path that never goes below height $0$ and ends at height $0$.

Let

$$F(x)=\sum_{n\ge 0}A_nx^n.$$

A first-step decomposition gives

$$F(x)=1+6xF(x)+x^2F(x)^2,$$

so

$$F(x)=\frac{1-6x-\sqrt{1-12x+32x^2}}{2x^2}.$$

Differentiating and rearranging gives

$$x(1-12x+32x^2)F'(x)+(2-18x+32x^2)F(x)-2=0.$$

Comparing coefficients of $x^n$ yields, for $n\ge 2$,

$$(n+2)A_n=6(2n+1)A_{n-1}-32(n-1)A_{n-2}.$$

The required value is the probability

$$R_n=\frac{A_n}{8^n}.$$

Dividing the recurrence by $8^n$ gives

$$(n+2)R_n=\frac{3(2n+1)}{4}R_{n-1}-\frac{n-1}{2}R_{n-2},$$

with $R_0=1$ and $R_1=\cfrac34$.

Modulo $998\,244\,353$, the numbers $2$, $4$, and every $n+2$ with $2\le n+2\le 100\,002$ are invertible. Hence the recurrence can be evaluated directly modulo the prime. If is the maximum input value, precompute once and answer each test case with .

The time complexity is $O(M+T)$ and the space complexity is $O(M+T)$.

Before reduction, the probability has denominator $8^N$. Therefore its reduced denominator is also coprime to $998\,244\,353$.

Solution written by GPT5.6