CF1436C Binary Search

Andrey 认为自己是一个非常成功的开发者，但实际上他直到最近才知道二分查找算法。在阅读了一些资料后，Andrey 明白了这个算法可以快速地在一个数组中查找某个数 $x$。对于一个从零开始编号的数组 $a$ 和一个整数 $x$，该算法的伪代码如下：  注意，数组的下标是从零开始的，且除法为整数除法（向下取整）。 Andrey 读到该算法只在数组有序时才有效。然而，他发现这个说法并不完全正确，因为确实存在一些无序数组，算法依然能找到 $x$！ Andrey 想给书的作者写信，但在此之前，他想要考虑长度为 $n$ 的排列中，算法能够找到 $x$ 的情况。一个长度为 $n$ 的排列是指一个包含 $1$ 到 $n$ 的 $n$ 个不同整数的数组，顺序任意。 请你帮助 Andrey，计算有多少个长度为 $n$ 的排列，满足 $x$ 恰好在下标 $pos$ 处，且上述二分查找算法能够找到 $x$（返回 true）。由于答案可能非常大，请输出对 $10^9+7$ 取余的结果。

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

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

第一个测试样例中所有可能的排列为：$(2, 3, 1, 4)$，$(2, 4, 1, 3)$，$(3, 2, 1, 4)$，$(3, 4, 1, 2)$，$(4, 2, 1, 3)$，$(4, 3, 1, 2)$。 由 ChatGPT 4.1 翻译