AT_agc059_f [AGC059F] LIDS

[problemUrl]: https://atcoder.jp/contests/agc059/tasks/agc059_f $ 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\ \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) $ です。