Bracketing Schemes

Farmer John has written an expression using N terms:

[ S = A_1 - A_2 - \cdots - A_N. ]

Betsy learned about addition, subtraction, and the use of parentheses. To test her understanding, Farmer John tells her that in the above expression exactly K pairs of parentheses were omitted. By inserting exactly K pairs of parentheses into the expression (in a valid, well‐formed way), one obtains a bracketing scheme. However, two schemes are considered essentially different if there exists a choice of values for \(A_1, A_2, \ldots, A_N\) such that the numerical values of the fully parenthesized expressions are different. (Otherwise, they are the same in essence.)

For example, consider the expression

[ S = A_1 - A_2 - A_3 - A_4. ]

When K = 2, one possible scheme is

[ S = (A_1) - A_2 - (A_3 - A_4), ]

which, after removing the redundant effect of parentheses (for example, note that (A₁) - A₂ - (A₃ - A₄) and (A₁ - A₂) - (A₃ - A₄) are essentially the same), yield a distinct effective outcome (namely, an expansion to a linear combination of \(A_i\) with coefficients \(+1\) or \(-1\)).

In fact, any fully parenthesized scheme of the expression will, after complete evaluation, yield an expression of the form

[ S = A_1 + \sum_{i=2}^{N} c_i A_i, \quad\text{where } c_i\in{+1,-1}. ]

A careful analysis shows that the essentially different outcomes correspond exactly to those sign selections that can be produced by inserting K pairs of parentheses in a valid way. It turns out that the outcome only depends on the positions of the toggles from the default sign (which is \(-1\) for every term \(A_i\) with \(i\ge2\)) to its opposite.

You are given two integers N and K. Compute the number of essentially different bracketing schemes that can result from inserting exactly K pairs of parentheses into the expression \(A_1-A_2-\cdots-A_N\>.

Note: If an outcome requires fewer than K non‐redundant parenthesis pairs in order to realize its sign changes, the remaining pairs may be inserted in a redundant fashion; hence that outcome is achievable with exactly K pairs as well.

A combinatorial argument shows that the answer is given by

[ \sum_{m=0}^{\min(K, N-1)} \binom{N-1}{m}, ]

since each nonredundant toggle (i.e. a change of sign for a contiguous block of terms beginning at some position) can be chosen among the N-1 gaps between terms, and only up to N-1 toggles can ever occur. In particular, if K ≥ N-1, all 2^(N-1) outcomes are achievable.

inputFormat

The input consists of a single line containing two integers N and K (where N is the number of terms in the expression, and K is the number of pairs of parentheses to insert).

It is guaranteed that N ≥ 1 and K ≥ 0.

outputFormat

Output a single integer: the number of essentially different bracketing schemes obtainable by inserting exactly K pairs of parentheses into the expression.

Hint: The answer is \(\sum_{m=0}^{\min(K, N-1)} \binom{N-1}{m}\).

sample

4 2

7