Andrey 认为他是一位真正成功的开发人员,但实际上他直到最近才知道二分搜索算法。在阅读了一些文献后,Andrey 了解到该算法可以快速找到数组中的某个数字 $$$x$$$。对于从零索引的数组 $$$a$$$ 和整数 $$$x$$$,算法的伪代码如下:
请注意,数组的元素从零开始索引,并且除法以整数进行(向下舍入)。
Andrey 读到该算法仅在数组已排序时才有效。然而,他发现这个说法不正确,因为肯定存在未排序的数组,算法可以找到$$$x$$$!
Andrey 想给本书作者写一封信,但在此之前,他必须考虑大小 $$$n$$$ 的排列,以便算法在其中找到 $$$x$$$。大小为 $$$n$$$ 的排列是由 $$$1$$$ 和 $$$n$$$ 之间的 $$$n$$$ 不同整数以任意顺序组成的数组。
帮助 Andrey 找到大小为 $$$n$$$ 的排列数,其中在位置 $$$pos$$$ 处包含 $$$x$$$,并且二分搜索算法的给定实现找到 $$$x$$$(返回 true)。由于结果可能非常大,因此打印除以 $$$10^9+7$$$ 的余数。
输入
输入的唯一行包含整数 $$$n$$$、$$$x$$$ 和 $$$pos$$$ ($$$1 \le x \le n \le 1000$$$, $$$0 \le pos \le n - 1$$$) — 分别是排列所需的长度、要搜索的数字以及该数字所需的位置。
输出
打印一个数字——有效排列数除以 $$$10^9+7$$$ 的余数。
示例
输入 #1
4 1 2
输出 #1
6
输入 #2
123 42 24
输出 #2
824071958
注意
第一个测试用例中所有可能的排列:$$$(2, 3, 1, 4)$$$, $$$(2, 4, 1, 3)$$$, $$$(3, 2, 1, 4)$$$, $$$(3, 4, 1, 2)$$$, $$$(4, 2, 1, 3)$$$, $$$(4、3、1、2)$$$。