考虑整数集合 $\{1, 2, \dots, n\}$ 以及它所有的 $k$ 元子集。我们将每个子集写为 $a_1, a_2, \dots, a_k$，其中 $a_1 < a_2 < \dots < a_k$。我们将这些子集按字典序逐行排列，得到一个有 $\binom{n}{k}$ 行和 $k$ 列的表格。令第 $i$ 行的第 $j$ 个整数为 $A_{i,j}$。

你的任务是计算给定列中相邻数字的绝对差之和。形式化地，给定一个正整数 $m$ ($1 \le m \le k$)，计算以下和：

$$\sum_{i=1}^{\binom{n}{k}-1} |A_{i,m} - A_{i+1,m}|$$

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入仅一行，包含三个正整数 $n, k$ 和 $m$ ($1 \le n \le 10^6, 1 \le m \le k \le n$)。

输出格式

输出一行，包含一个整数：问题的答案对 $10^9 + 7$ 取模的结果。

样例

输入格式 1

4 2 2

输出格式 1

4

说明

在第一个样例中，表格如下所示：

1 2 1 3 1 4 2 3 2 4 3 4

答案为 $|2 - 3| + |3 - 4| + |4 - 2| + |2 - 3| + |3 - 4| = 4$。

输入格式 2

5 3 2

输出格式 2

4