Glove Selection

You are given n pairs of distinct gloves. Each pair consists of a left glove and a right glove. You need to determine the number of ways to select exactly m gloves such that exactly k complete pairs are included among the selected gloves.

Note that every glove is considered unique, even though two gloves from the same pair are considered to form a complete pair.

Explanation:

If you choose exactly k complete pairs, then you have taken 2k gloves from those pairs. The remaining m-2k gloves should be selected from the remaining n-k pairs, taking at most one glove from each pair (so that no additional complete pair is formed). In other words, you first select k pairs from n pairs, and then from the remaining pairs, choose m-2k pairs and decide whether to take the left or right glove from each selected pair.

The mathematical formula to compute the answer is:

[ answer = \binom{n}{k} \times \binom{n-k}{m-2k} \times 2^{m-2k} ]

If the parameters do not allow such a selection (for example, if m > 2n or if m-2k is negative or greater than n-k), the answer is 0.

inputFormat

The input consists of a single line containing three integers n, m, and k, where:

• n is the number of glove pairs,
• m is the total number of gloves to choose, and
• k is the number of complete pairs that must be included in the selection.

outputFormat

Output a single integer representing the number of ways to select the gloves such that exactly k complete pairs are included.

sample

3 3 1

12