配点 : $1900$ 点

問題文

$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$ の最長減少部分列の長さを表します。

制約

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

入力

入力は標準入力から以下の形式で与えられる。

$N$ $pos$ $val$

出力

答えを出力せよ。

3 2 2

2

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

4 1 1

6

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

5 2 5

11

2022 69 420

128873576