Faint

정수 집합 $\{1, 2, \ldots, n\}$의 크기 $k$인 부분집합을 모두 생각하자. 각 부분집합을 $a_1 < a_2 < \ldots < a_k$인 $a_1, a_2, \ldots, a_k$로 쓴다. 이 부분집합들을 사전순으로 한 줄에 하나씩 적어 ${n \choose k}$개의 행과 $k$개의 열로 이루어진 표를 얻는다. $i$번째 행의 $j$번째 정수를 $A_{i, j}$라 하자.

주어진 열에서 이웃한 두 수의 차의 절댓값의 합을 구해야 한다. 양의 정수 $m$ ($1 \le m \le k$)이 주어질 때, 다음 값을 계산하라. $\sum\limits_{i = 1}^{{n \choose k} - 1} |A_{i, m} - A_{i + 1, m}|\text{.}$ 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 세 양의 정수 $n$, $k$, $m$이 주어진다. ($1 \le n \le 10^6, 1 \le m \le k \le n$)

답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서 표는 다음과 같다.

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

답은 $|2 - 3| + |3 - 4| + |4 - 3| + |3 - 4| + |4 - 4| = 4$이다.