P1722 Matrix II

Adapted series by usqwedf.

If you are reading this in a rush, please jump to the sixth line. As is well known, in ancient Chinese counting rods, red means positive and black means negative. Given a $1 \times 2n$ matrix (usqwedf: isn't this just a sequence of length $2n$?), you may freely place red and black counting rods so that the matrix is balanced (i.e., for all $i \in [1, 2n]$, in positions $1$ to $i$, the number of red rods is greater than or equal to the number of black rods). How many placements satisfy the balance condition (note that the numbers of red and black rods must be equal)?

A positive integer $n$.

The value of $t$ modulo $100$, where $t$ is the number of valid placements.

Sample explanation: - Scheme 1: Red, Black, Red, Black. - Scheme 2: Red, Red, Black, Black. Constraints: $1 \le n \le 100$. Translated by ChatGPT 5