[CEOI2016] kangaroo
题目描述
有一个园子,里面有 $n$ 个草丛排成一排,标号 $1\sim n$,有一个袋鼠,从 $s$ 出发,每次跳一步跳到一个其他的草丛,经过每个草丛恰好一次,最终到达 $t$。显然他会跳跃 $n-1$ 次。为了不被人类发现,袋鼠每次跳跃的方向必须与前一次不同。
具体地,如果他现在在 $now$,他是从 $prev $ 跳跃一次到达 $now$ 的,然后他跳跃一次到达 $next$:
- 那么如果 $prev<now$,就必须有 $next<now$;
- 如果 $now<prev$,就必须有 $now<next$。
问从 $s$ 到 $t$ 的方案数模 $10^9+7$ 的结果。
两个路线不同,当且仅当草丛被访问的顺序不同。
保证至少有一种方案。
初始时可以往任意方向跳。
输入输出格式
输入格式
一行三个整数 $n,s,t$。
输出格式
一行一个整数,代表答案。
输入输出样例
输入样例 #1
4 2 3
输出样例 #1
2
说明
对于 $100\%$ 的数据,$2\le n\le 2\times 10^3$,$1\le s,t\le n$