Description

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)?

Input Format

A positive integer $n$.

Output Format

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

2

2

Hint

Sample explanation:

• Scheme 1: Red, Black, Red, Black.
• Scheme 2: Red, Red, Black, Black.

Constraints:

$1 \le n \le 100$.

Translated by ChatGPT 5