← 返回题目列表

AtCoder · agc059_f

F. 盖子

中文机器翻译题面 查看原题

分数: 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