問題文

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

出力

答えを出力せよ。

入力例 1

3 2 2

出力例 1

2

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

入力例 2

4 1 1

出力例 2

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

入力例 3

5 2 5

出力例 3

11

入力例 4

2022 69 420

出力例 4

128873576