题目描述

Anton 参加程序设计竞赛已经很久了。一周后，他将参加确定国家队名单的选拔赛。某天他在做之前一次选拔赛的题目时，发现其中一小部分可以归结为二分查找。

作为一名有经验的选手，他很快写出了如下 C++ 二分查找实现：

int binary_search(vector<int> &a, int value) {
   int l = 0;
   int r = (int)a.size() - 1;
   while (l <= r) {
      int m = (l + r + 1) / 2;
      if (a[m] == value)
         return m;
      else if (a[m] > value)
         r = m - 1;
      else
         l = m + 1;
   }
   return -1;
}

在测试这段代码之前，Anton 意识到他的整数数组 a 实际上并没有排序。幸运的是，他很快想到了如何解决这个问题。但随后他产生了一个问题：

对于一个没有排序的整数数组，上面这份二分查找实现能够正确工作的概率是多少？

由于概率论并不是他最喜欢的内容，他先把问题形式化为下面这个计数问题。

给定 $N$ 和 value，考虑整数 $1$ 到 $N$ 的所有排列。请问有多少个排列满足：上面这份 binary_search 返回的下标 $i$ 满足 $a[i]=\text{value}$？

答案可能很大，你只需要输出答案对 $1\,000\,000\,007$ 取模后的结果。

请编写程序 binsearch 解决该问题。

输入格式

输入只有一行，包含两个正整数 $N$ 和 value，用空格分隔。

保证 $1 \le \text{value} \le N$。

输出格式

设 $P_N$ 为满足条件的排列数量。

输出一行一个整数，表示 $P_N$ 对 $1\,000\,000\,007$ 取模的结果。

数据范围

• $1 \le N \le 10\,000$；
• $1 \le \text{value} \le N$；
• 在 $10\%$ 的测试中，$1 \le N \le 10$；
• 在 $20\%$ 的测试中，$1 \le N \le 20$；
• 在 $50\%$ 的测试中，$1 \le N \le 100$；
• 在 $75\%$ 的测试中，$1 \le N \le 1000$。

样例 1

输入

3 1

输出

4

样例 2

输入

5 2

输出

66

样例 3

输入

7 1

输出

2160

样例 4

输入

9 4

输出

135360

样例说明

对于样例 1，集合 $\{1,2,3\}$ 的 $6$ 个排列分别是：

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

其中 Anton 的二分查找只在两个排列上不能正确找到 value=1：

(2, 3, 1), (3, 2, 1)

因此正确工作的排列数量为 $6-2=4$，输出 $4$。