P1754 Fans Ticket Purchase Problem

A grand football match is about to take place. A long line of fans has formed at the ticket office. According to the rules of the ticket office, each buyer may purchase at most one ticket, and each ticket costs $50$ yuan. In the line, there are $n$ people holding $50$-yuan bills and another $n$ people holding $100$-yuan bills. Suppose the ticket office has no change at the start of sales. How many queueing orders of these $2n$ fans will ensure the ticket office never faces the embarrassment of being unable to make change? For example, when $n=2$, let A denote a fan holding a $50$-yuan bill and B denote a fan holding a $100$-yuan bill. Then there are at most the following two different queueing orders that ensure the clerk can always make change. - First: $\mathtt{[A,A,B,B]}$. - Second: $\mathtt{[A,B,A,B]}$. Given $n$, compute how many queueing orders of $2n$ fans will ensure the ticket office can always make change.

A single integer representing the value of $n$.

A single integer, the number of valid queueing orders.

### Constraints and Conventions For all testdata, $0 \le n \le 20$. Translated by ChatGPT 5