[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$