Description

想象你在一栋有 $n$ 层的楼里，你可以乘坐电梯在楼层之间移动。让我们从下到上用整数从 $1$ 到 $n$ 对楼层进行编号。现在你在 $a$ 楼。你很无聊，所以想乘坐电梯。$b$ 楼有一个秘密实验室，禁止进入。然而，你已经心情激动，决定乘坐电梯进行 $k$ 次连续旅行。

假设你现在在 $x$ 楼（最初你在 $a$ 楼）。为了在楼层之间进行另一次旅行，你可以选择一个编号为 $y$ 的楼层（$y ≠ x$），电梯就会前往这个楼层。因为你不能访问秘密实验室所在的 $b$ 楼，所以你决定从当前楼层 $x$ 到所选楼层 $y$ 的距离必须严格小于从当前楼层 $x$ 到秘密实验室所在的 $b$ 楼的距离。正式地说，这意味着以下不等式必须满足：$|x - y| < |x - b|$。电梯成功将你运送到 $y$ 楼后，你将 $y$ 的编号写在你的笔记本上。

你的任务是找到你可以在笔记本上写下的不同数字序列的数量，这些序列可以是电梯的 $k$ 次旅行的结果。由于所寻求的旅行次数可能相当大，请找到将数字除以 1000000007（10^9 + 7）后的余数。

Format

Input

输入的第一行包含四个空格分隔的整数 $n$, $a$, $b$, $k$（$2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b$）。

Output

打印一个整数——所寻求的序列数量除以 1000000007（10^9 + 7）后的余数。

Samples

示例1

输入:

5 2 4 1

输出:

2

示例2:

输入：

5 2 4 2

输出:

2

示例3:

输入：

5 3 4 1

输出:

0

$注:$

两个序列 $p_1, p_2, ..., p_k$ 和 $q_1, q_2, ..., q_k$ 是不同的，如果存在这样的整数 $j（1 ≤ j ≤ k）$，使得 $p_j ≠ q_j$。

示例说明:

在第一个示例中，第一次旅行后，你可以在第 1 层或第 3 层，因为 |1 - 2| < |2 - 4| 和 |3 - 2| < |2 - 4|。

在第二个示例中，有两种可能的序列：（1, 2）；（1, 3）。你不能在第一次旅行中选择第 3 层，因为在这种情况下，没有楼层可以作为第二次旅行的楼层。

在第三个示例中，没有所寻求的序列，因为你无法选择第一次旅行的楼层。

Limitation

$时间限制:$ 2 秒 $内存限制:$ 256 MB