分数: 1900 点
问题陈述
鉴于 N, pos, val,求排列数 P=(P_1, P_2, \ldots, P_N) of (1,2,\ldots,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