题目描述

给定排成一行的 $N$ 个位置 ，编号为 $1 \sim N（N \geq 2）$

机器人初始位于 $M$ 位置$（1 \leq M \leq N）$。

如果机器人在 $1$ 位置，下一步只能往右到 $2$ 位置；

如果机器人在 $N$ 位置，下一步只能往左到 $N - 1$ 位置；

在中间位置时，下一步可往左或往右。

规定机器人必须走 $K$ 步，求最终能到达 $P$ 位置$（1 \leq P \leq N）$的方法数

最终答案方案数对 $1000000007$ 取模

下图为 $N=7,M=4,P=6$ 的情况

输入格式

输入共一行，包含四个整数 $N、M、K、P$，分别表示位置总数、机器人初始位置、行走步数和目标位置。

输出格式

输出一个整数，表示到达目标位置的方法数，输出取模后的结果

样例

6 2 4 4 

4

5 3 3 4

3

提示

样例1解释

• 6个位置，从2走到4，只能走4步，方案如下
  • 2->3->4->5->4
  • 2->3->2->3->4
  • 2->1->2->3->4
  • 2->3->4->3->4
• 共4种走法

样例2解释

• 5个位置，从3走到4，只能走3步，方案如下
  • 3->4->5->4
  • 3->4->3->4
  • 3->2->3->4
• 共3种走法

数据范围

$2 <= N <= 1000$

$1 <= M <= N$

$1 <= K <= 1000$

$1 <= P <= N$