题目描述

假设你现在在一栋有 $n$ 层的楼里，可以乘坐电梯在各层之间移动。我们将楼层自下而上编号为 $1$ 到 $n$。你目前在第 $a$ 层。你感到很无聊，于是想乘坐电梯。第 $b$ 层有一间秘密实验室，不允许进入。不过你已经玩嗨了，决定连续坐 $k$ 次电梯。

假设你当前在第 $x$ 层（最初你在第 $a$ 层）。在每一次电梯旅行中，你选择某一不同于 $x$ 的楼层 $y$（即 $y \ne x$），电梯会把你送到那里。因为你不能经过有秘密实验室的 $b$ 层，所以你决定移动距离 $|x-y|$ 必须严格小于当前所在楼层到 $b$ 层的距离 $|x-b|$。即，必须满足 $|x-y| < |x-b|$。每当你成功移动到 $y$ 层时，你会把 $y$ 记到你的笔记本上。

你的任务是，计算经过 $k$ 次电梯旅行后，你可能在笔记本上记录下的不同数字序列个数。由于最终序列数可能非常大，请将其结果对 $1000000007$（$10^9+7$）取模后输出。

输入格式

输入的第一行为四个用空格分隔的整数 $n$、$a$、$b$、$k$，其中 $2 \leq n \leq 5000$，$1 \leq k \leq 5000$，$1 \leq a, b \leq n$，且 $a \ne b$。

输出格式

输出一个整数，表示不同数字序列的总个数，对 $1000000007$ 取模。

输入输出样例 #1

输入 #1

5 2 4 1

输出 #1

2

输入输出样例 #2

输入 #2

5 2 4 2

输出 #2

2

输入输出样例 #3

输入 #3

5 3 4 1

输出 #3

0

说明

两个序列 $p_1, p_2, \dots, p_k$ 和 $q_1, q_2, \dots, q_k$ 被认为是不同的，如果存在某个整数 $j$（$1 \le j \le k$），使得 $p_j \neq q_j$。

样例说明：

1. 第一个样例中，第一次乘梯后你可能到达第 1 层或第 3 层，因为 $|1 - 2| < |2 - 4|$ 且 $|3 - 2| < |2 - 4|$。
2. 第二个样例中，有两种可能的序列：$(1, 2)$ 和 $(1, 3)$。第一次不能直接选第 3 层，因为那样第二次就没法选楼层了。
3. 第三个样例中，没有符合条件的序列，因为第一次就无法选楼层。

数据范围

$ 50\%$的数据，$2 \leq n \leq 500$,$1 \leq k \leq 500$ . $ 100\%$的数据: $2 \leq n \leq 5000$，$1 \leq k \leq 5000$，$1 \leq a, b \leq n$，且 $a \ne b$