19087번 - Faint 다국어

Consider the set of integers $\{1, 2, \ldots, n\}$ and all its subsets of size $k$. Let us write each such subset as $a_1, a_2, \ldots, a_k$ where $a_1 < a_2 < \ldots < a_k$. We write them down in lexicographical order row by row, obtaining a table with ${n \choose k}$ rows and $k$ columns. Let the $j$-th integer in the $i$-th row be $A_{i, j}$.

Your task is to calculate the sum of absolute differences between consecutive numbers in a given column. Formally, given a positive integer $m$ ($1 \le m \le k$), calculate the sum $$\sum\limits_{i = 1}^{{n \choose k} - 1} |A_{i, m} - A_{i + 1, m}|\text{.}$$ As the answer can be very large, print it modulo $10^9 + 7$.

The only line of input contains three positive integers $n$, $k$ and $m$ ($1 \le n \le 10^6, 1 \le m \le k \le n$).

Print a single line with a single integer: the answer to the problem modulo $10^9 + 7$.

In the first example, the table looks as follows.

$$\begin{array}{cc} 1 & 2 \\ 1 & 3 \\ 1 & 4 \\ 2 & 3 \\ 2 & 4 \\ 3 & 4 \\ \end{array}$$

The answer is $|2 - 3| + |3 - 4| + |4 - 3| + |3 - 4| + |4 - 4| = 4$.