YZOJ P3129 [校内训练20170627]跳格子

时间限制：1000MS 内存限制：524288KB

难度：$7.0$

• 题目描述

在一个花园里有一排 $n$ 个格子，这些格子编号为 $1$ 到 $n$ 。袋鼠喜欢在花园的格子上跳跃。

袋鼠的跳跃方式是这样的：一开始，袋鼠位于 $s$ 号格子上，接着它会选择一个尚未经过的格子上跳跃，经过 $n-1$ 次跳跃后，所有格子都被经过了一次，袋鼠的跳跃将结束。袋鼠总是会在 $t$ 号格子结束跳跃。

由于袋鼠中了病毒，所以如果上一步往前跳，那么这一步必须往后跳；反之，若上一步往后跳，那么这一步往前跳。

请问袋鼠有多少种跳跃的方案呢？

形式化地，你需要求出有多少个 $1$ 到 $n$ 的排列 $p_1, p_2, \cdots, p_n$，满足：

1， $p_1=s ，p_n=t$；

2， 对任意 $2 \leq i \leq n-1$，或者 $(p_i-1<p_i) \land (p_i+1<p_i)$ ，或者 $(p_i-1>p_i) \land (p_i+1>p_i)$ 。

• 输入格式

输入共一行，包含三个正整数 $n, s, t$ 。

• 输出格式

输出共一行，包含一个整数，表示跳跃的方案数对 $1,000,000,007$ 取模的结果。

• 样例输入【包含两组样例】

• 样例输出

• 样例 1 说明

从 $2$ 号格子到 $3$ 号格子的跳跃方案有两种，一种是 $2,1,4,3$，一种是 $2,4,1,3$ 。

• 数据规模与约定

 

 

 …