问题描述

给定排成一行的 $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、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 <= N <= 1000$

$1 <= M <= N$

$1 <= K <= 1000$

$1 <= P <= N$