题目描述

$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$

输出格式

答えを出力せよ。

题目大意

求满足下列要求的 $N$ 阶排列 $P$ 的个数：

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

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

答案对 $10^9+7$ 取模。

3 2 2

2

4 1 1

6

5 2 5

11

2022 69 420

128873576

提示

制約

• $1\ \le\ N\ \le\ 5\cdot\ 10^6$
• $1\ \le\ pos,\ val\ \le\ N$
• 入力中のすべての値は整数である。

Sample Explanation 1

条件を満たす順列は $(1,\ 2,\ 3),\ (3,\ 2,\ 1)$ です。

Sample Explanation 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) $ です。