P5999 [CEOI 2016] kangaroo

There is a garden with $n$ bushes in a line, numbered $1 \sim n$. A kangaroo starts from $s$, and each time it jumps one step to a different bush, visiting every bush exactly once, and finally arrives at $t$. Obviously, it will jump $n - 1$ times. In order not to be discovered by humans, the direction of each jump must be different from the previous one. More specifically, if it is currently at $now$, it jumped from $prev$ to reach $now$, and then it jumps to $next$: - If $prev < now$, then it must hold that $next < now$. - If $now < prev$, then it must hold that $now < next$. Ask for the number of valid routes from $s$ to $t$ modulo $10^9 + 7$. Two routes are different if and only if the visiting order of the bushes is different. It is guaranteed that there is at least one valid route. At the beginning, it may jump in any direction.

One line with three integers $n, s, t$.

One line with one integer, representing the answer.

For $100\%$ of the testdata, $2 \le n \le 2 \times 10^3$, $1 \le s, t \le n$. Translated by ChatGPT 5