/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 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
Score : 1900 points
Problem Statement
Given N, pos, val, find the number of permutations P=(P_1, P_2, \ldots, P_N) of (1,2,\ldots,N) that satisfy all of the following conditions, modulo 10^9+7:
- LIS(P) + LDS(P) = N+1
- P_{pos} = val
Here, LIS(P) denotes the length of the longest increasing subsequence of P, and LDS(P) denotes the length of the longest decreasing subsequence of P.
Constraints
- 1 \le N \le 5\cdot 10^6
- 1 \le pos, val \le N
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N pos val
Output
Print the answer.
Sample Input 1
3 2 2
Sample Output 1
2
The following permutations satisfy the conditions: (1, 2, 3), (3, 2, 1).
Sample Input 2
4 1 1
Sample Output 2
6
The following permutations satisfy the conditions: (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2).
Sample Input 3
5 2 5
Sample Output 3
11
Sample Input 4
2022 69 420
Sample Output 4
128873576