题目描述

一行共有 $N$ 个格子，从左到右从 $1$ 到 $N$ 编号。一只袋鼠从 $c_s$ 出发，经过恰好 $N-1$ 次跳跃，到达 $c_f$，并且经过所有的 $N$ 个格子，每次跳跃的方向都与上一次不同。如果袋鼠当前所在的格子为 $\text{current}$，来自 $\text{prev}$，则其下一个格子 $\text{next}$ 满足：

• 如果 $\text{prev} < \text{current}$，则 $\text{next} < \text{current}$；
• 如果 $\text{current} < \text{prev}$，则 $\text{current} < \text{next}$。

求不同的跳跃方案数除以 $1000000007\ (10^9+7)$ 的余数。

输入格式

一行三个正整数 $N, c_s, c_f$.

输出格式

一行一个整数，表示袋鼠的不同路线数模 $100000007\ (10^9+7)$ 的余数。

4 2 3

2

数据范围与提示

• $2 \le N \le 2000$
• $1 \le c_s \le N$
• $1 \le c_f \le N$
• $c_s \neq c_f$
• 对于 $6\%$ 的测试数据，$N \le 6$。
• 对于 $36\%$ 的测试数据，$N \le 40$。
• 对于 $51\%$ 的测试数据，$N \le 200$。
• 两条路线不同当且仅当访问各个格子的顺序不同。
• 数据保证至少有一条符合要求的路线。
• 袋鼠第一次从 $c_s$ 开始可以向任意方向跳跃。