#13. 【NFLSPC #0】Permutation

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

给定 $n,\ x,\ y$,求 $1,\ 2,\ 3,\ \dots,\ n$ 的每一个全排列 $a_1,\ a_2,\ a_3,\ \dots,\ a_n$ 中满足如下性质的排列个数:

  1. 第一个数为 $x$ ;
  2. 最后一个数为 $y$ ;
  3. 对于第 $i$ 个数 $a_i\ (2\ \leq\ i\ \leq\ n\ -\ 1)$,要么 $a_i\ >\ a_{i\ -\ 1}$ 且 $a_i\ >\ a_{i\ +\ 1}$ 或者$a_i\ <\ a_{i\ -\ 1}$ 且 $a_i\ <\ a_{i\ +\ 1}$。

由于答案可能过大,输出其对 $10^9\ +\ 7$ 取模的结果。


输入格式

一行,三个数$n,\ x,\ y$

输出格式

一行,一个数,表示答案对 $10^9\ +\ 7$ 取模的结果。


样例一

Input

4 1 4

Output

1

Explanation

只有一个符合要求的排列:${1,\ 3,\ 2,\ 4}$


样例二

Input

6 2 5

Output

6

样例三

Input

1926 8 17

Output

624920900

Explanation

注意对$10^9\ +\ 7$取模


限制与约定

对于 $10\%$ 的数据,满足 $n\ =\ 3$。

对于另外 $20\%$ 的数据,满足 $n\ \leq\ 10$。

对于另外 $10\%$ 的数据,满足 $n\ =\ 12$。

对于另外 $10\%$ 的数据,满足 $n\ =\ 13$。

对于另外 $10\%$ 的数据,满足 $n\ =\ 14$。

对于另外 $10\%$ 的数据,满足 $n\ =\ 15$。

对于 $100\%$ 的数据,满足 $1\ \leq\ x,\ y\ \leq\ n\ \leq\ 2000,\ x\ \neq\ y$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$