题目描述

给定 $N$、$pos$、$val$，请计算满足以下所有条件的 $(1,2,\ldots,N)$ 的排列 $P=(P_1,\ P_2,\ \ldots,\ P_N)$ 的个数，并将结果对 $10^9+7$ 取模。

• $LIS(P) + LDS(P) = N+1$
• $P_{pos} = val$

其中，$LIS(P)$ 表示 $P$ 的最长上升子序列的长度，$LDS(P)$ 表示 $P$ 的最长下降子序列的长度。

输入格式

输入从标准输入读取，格式如下：

$N$ $pos$ $val$

输出格式

请输出答案。

样例 1

输入

3 2 2

输出

2

样例 2

输入

4 1 1

输出

6

样例 3

输入

5 2 5

输出

11

样例 4

输入

2022 69 420

输出

128873576

说明/提示

限制条件

• $1 \leq N \leq 5 \cdot 10^6$
• $1 \leq pos, val \leq N$
• 输入中的所有值均为整数。

样例解释 1

满足条件的排列为 $(1, 2, 3), (3, 2, 1)$。

样例解释 2

满足条件的排列为 $(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)$。

由 ChatGPT 4.1 翻译