AT_agc059_f [AGC059F] LIDS

给定 $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 \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 翻译