A5882. 「CEOI2016」袋鼠
编程题
省选/NOI-
知识点
题目描述
一行共有 $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)$ 的余数。
* 如果 $\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)$ 的余数。
输入输出样例
输入 #1
4 2 3
输出 #1
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$ 开始可以向任意方向跳跃。
* $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$ 开始可以向任意方向跳跃。