Description

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.

Input Format

A single integer representing the value of $n$.

Output Format

A single integer, the number of valid queueing orders.

2

2

Hint

Constraints and Conventions

For all testdata, $0 \le n \le 20$.

Translated by ChatGPT 5