题目描述

给定 $N, pos, val$，找到满足以下条件的排列 $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