题目描述

对于一个从 零开始编号 的数组 $a$ 和一个整数 $x$，二分算法查找 $x$ 的伪代码如下：

可能和常规的二分查找模板不同，可自行模拟体会。

1 BinarySearch(a, x)
2     left = 0
3     right = a.size()
4     while left < right
5         middle = (left + right) / 2
6         if a[middle] <= x then
7             left = middle + 1
8         else
9             right = middle
10    if left > 0 and a[left - 1] == x then
11        return true
12    else 
13        return false

注意，数组的下标是从零开始的。

众所周知该算法只在 数组有序时 才有效。然而，翁老师发现这个说法并不完全正确，因为确实存在一些无序数组，算法依然能找到 $x$！

因此翁老师想给二分算法的作者写信，但在此之前，他想要考虑长度为 $n$ 的排列中，算法能够找到 $x$ 的情况。一个长度为 $n$ 的排列是指一个包含 $1$ 到 $n$ 的 $n$ 个不同整数的数组，顺序任意。

请你帮助 翁老师，计算有多少个长度为 $n$ 的排列，满足 $x$ 恰好在下标 $pos$ 处，且上述二分查找算法能够找到 $x$（返回 true）。由于答案可能非常大，请输出对 $10^9+7$ 取余的结果。

输入格式

输入仅一行，包含三个整数 $n$、$x$ 和 $pos$，分别表示排列的长度、要查找的数字以及该数字所在的位置。

输出格式

输出一个整数，表示满足条件的排列数对 $10^9+7$ 取余后的结果。

4 1 2

6

样例 1 解释

可以证明这 $6$ 个排列运行上述二分程序都能在 $pos=2$ 的位置找到 $x=1$。

• $(2, 3, 1, 4)$
• $(2, 4, 1, 3)$
• $(3, 2, 1, 4)$
• $(3, 4, 1, 2)$
• $(4, 2, 1, 3)$
• $(4, 3, 1, 2)$

123 42 24

824071958

提示

数据范围

对于 $100\%$ 的数据范围满足：$1 \le x \le n \le 10^3$，$0 \le pos \le n-1$。

本题测试点较多，部分测试点满足：$n\leq 10$ 或 $x=1$ 或 $x=n$。