P2270 [HNOI2002] Cow's Arithmetic

Recently, the cows on Farmer John's farm have been taking a basic math class. One day, the cow Besty learned addition, subtraction, and how to use parentheses. To test Besty's learning, Farmer John wrote the following expression: $S =A_1-A_2-\ldots-A_n$ Then Farmer John told Besty that $K$ pairs of parentheses were omitted in this expression. Adding these $K$ pairs of parentheses to the expression produces one expression scheme. For example: $S=A_1-A_2-A_3-A_4$, $K = 2$, then $S = (A_1)-A_2 - (A_3- A_4)$ is one such scheme. For any two expression schemes, $S'$ and $S''$, they are essentially different if there exists a sequence $A_1, \ldots, A_n$ such that $S' \ne S''$. Otherwise, they are essentially the same. For example, $S'=(A_1)-A_2-(A_3-A_4)$ and $S''=(A_1-A_2)-(A_3-A_4)$ are essentially the same schemes. Now, Farmer John tells Besty the number of terms $N$ and the number of pairs of parentheses $K$ in the expression (the sequence $A$ is variable; we do not need to care about it). He wants to test how many essentially different expression schemes there are.

The input contains a single line with two integers $N$ and $K$。($1

Output a single line containing the number of essentially different expression schemes.

Translated by ChatGPT 5