CF1436C.Binary Search

Andrey thinks he is truly a successful developer, but in reality he didn't know about the binary search algorithm until recently. After reading some literature Andrey understood that this algorithm allows to quickly find a certain number $x$ in an array. For an array $a$ indexed from zero, and an integer $x$ the pseudocode of the algorithm is as follows:

Note that the elements of the array are indexed from zero, and the division is done in integers (rounding down).

Andrey read that the algorithm only works if the array is sorted. However, he found this statement untrue, because there certainly exist unsorted arrays for which the algorithm find $x$!

Andrey wants to write a letter to the book authors, but before doing that he must consider the permutations of size $n$ such that the algorithm finds $x$ in them. A permutation of size $n$ is an array consisting of $n$ distinct integers between $1$ and $n$ in arbitrary order.

Help Andrey and find the number of permutations of size $n$ which contain $x$ at position $pos$ and for which the given implementation of the binary search algorithm finds $x$ (returns true). As the result may be extremely large, print the remainder of its division by $10^9+7$.

安德烈认为自己是一位真正成功的开发者，但实际上直到最近他才了解到二分查找算法。在阅读了一些资料后，安德烈明白了该算法可以快速在数组中查找某个数 $x$。对于一个从下标 0 开始索引的数组 $a$ 和一个整数 $x$，该算法的伪代码如下：

注意：数组元素的下标从 0 开始，且除法为整数除法（向下取整）。

安德烈读到，该算法仅在数组已排序时才有效。然而，他发现这一说法并不正确，因为显然存在一些未排序的数组，使得该算法仍能成功找到 $x$！

安德烈打算给这本书的作者写一封信，但在动笔之前，他必须先考虑所有大小为 $n$ 的排列，使得该算法能在其中找到 $x$。大小为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数组成、顺序任意的数组。

请帮助安德烈，求出满足以下条件的大小为 $n$ 的排列的个数：其中 $x$ 位于位置 $pos$，且上述二分查找算法能成功找到 $x$（即返回 true）。由于结果可能极大，请输出其对 $10^9+7$ 取模后的余数。

The only line of input contains integers $n$, $x$ and $pos$ ($1 \le x \le n \le 1000$, $0 \le pos \le n - 1$) — the required length of the permutation, the number to search, and the required position of that number, respectively.

输入仅有一行，包含整数 $n$、$x$ 和 $pos$（$1 \le x \le n \le 1000$，$0 \le pos \le n - 1$），分别表示所要求的排列长度、待搜索的数字，以及该数字所需位于的位置。

Print a single number — the remainder of the division of the number of valid permutations by $10^9+7$.

输出一个整数——有效排列的数目对 $10^9+7$ 取模的余数。

All possible permutations in the first test case: $(2, 3, 1, 4)$, $(2, 4, 1, 3)$, $(3, 2, 1, 4)$, $(3, 4, 1, 2)$, $(4, 2, 1, 3)$, $(4, 3, 1, 2)$.

第一个测试用例中所有可能的排列：$(2, 3, 1, 4)$、$(2, 4, 1, 3)$、$(3, 2, 1, 4)$、$(3, 4, 1, 2)$、$(4, 2, 1, 3)$、$(4, 3, 1, 2)$。