UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4934. [Ceoi2016]kangaroo

Statistics 下载数据

Description

有一个园子,里面有n个草丛排成一排,标号1~n,有一个袋鼠,从s出发,每次跳一步跳到一个其他的草丛,经过
每个草丛恰好一次,最终到达t。显然他会跳跃n-1次为了不被人类发现,袋鼠每次跳跃的方向必须与前一次不同,
具体地,如果他现在在now,他是从prev跳跃一次到达now的,然后他跳跃一次到达next,那么如果prev<now,就必
须有now<next,如果now<prev,就必须有next<now问从s到t的方案数,模1e9+7两个路线不同,当且仅当草丛被访
问的顺序不同保证至少有一种方案初始时可以往任意方向跳。
修正下:那么如果prev<now,就必须有next<now

如果now<prev,就必须有now<next

Input

 一行三个整数,n,s,t

2<=n<=2000
1<=s<=n
1<=t<=n

Output

 一行一个整数,代表答案

Sample Input

4 2 3

Sample Output

2

Hint

Source

鸣谢alone_wolf提供翻译