CF479E.Riding in a Lift

Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.

Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y ≠ x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x - y| < |x - b|. After the lift successfully transports you to floor y, you write down number y in your notepad.

Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109 + 7).

假设你身处一栋恰好有 $n$ 层的建筑中，可通过电梯在楼层之间移动。我们从下到上将楼层依次编号为 $1$ 至 $n$。当前你位于第 $a$ 层。你感到非常无聊，因此决定乘坐电梯。第 $b$ 层设有一间秘密实验室，禁止入内。然而，你兴致已起，决定连续乘坐电梯 $k$ 次。

假设当前你位于第 $x$ 层（初始时你在第 $a$ 层）。在下一次电梯行程中，你需选择一个楼层 $y$（满足 $y \ne x$），电梯将把你运送到该楼层。由于你不能访问设有秘密实验室的第 $b$ 层，你规定：从当前楼层 $x$ 到所选楼层 $y$ 的距离必须严格小于从当前楼层 $x$ 到秘密实验室所在楼层 $b$ 的距离。形式化地，该条件表示为不等式：

$$|x - y| < |x - b|$$

当电梯成功将你送达楼层 $y$ 后，你便将数字 $y$ 记录在笔记本中。

你的任务是：求出经过 $k$ 次电梯行程后，笔记本中可能写出的互不相同的数字序列的总数。由于该数目可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line of the input contains four space-separated integers n, a, b, k (2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b).

输入的第一行包含四个以空格分隔的整数 $n$、$a$、$b$、$k$（$2 \leq n \leq 5000$，$1 \leq k \leq 5000$，$1 \leq a, b \leq n$，$a \neq b$）。

Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).

输出一个整数——所求序列数量对 1000000007（$10^9 + 7$）取模后的余数。

Two sequences _p_1, _p_2, ..., p__k and _q_1, _q_2, ..., q__k are distinct, if there is such integer j (1 ≤ j ≤ k), that p__j ≠ q__j.

Notes to the samples:

1. In the first sample after the first trip you are either on floor 1, or on floor 3, because |1 - 2| < |2 - 4| and |3 - 2| < |2 - 4|.
2. In the second sample there are two possible sequences: (1, 2); (1, 3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip.
3. In the third sample there are no sought sequences, because you cannot choose the floor for the first trip.

两个序列 $p_1,\,p_2,\,\dots,\,p_k$ 和 $q_1,\,q_2,\,\dots,\,q_k$ 被称为互异的，当且仅当存在某个整数 $j$（满足 $1\le j\le k$），使得 $p_j\ne q_j$。

样例说明：

1. 在第一个样例中，第一次移动后，你位于第 1 层或第 3 层，因为 $|1-2|<|2-4|$ 且 $|3-2|<|2-4|$。
2. 在第二个样例中，存在两种可能的序列：$(1,\,2)$ 和 $(1,\,3)$。你不能在第一次移动时选择第 3 层，因为此时无法为第二次移动选择任何楼层。
3. 在第三个样例中，不存在满足条件的序列，因为你无法为第一次移动选择任何楼层。