← 返回题目列表

Codeforces · 479/E

E. 乘坐电梯

中文机器翻译题面 查看原题

想象一下,您在一栋恰好有 n 层的建筑物中。您可以乘坐电梯在楼层之间移动。让我们用 1 到 n 的整数从下到上对楼层进行编号。现在你在a层。你很无聊,所以你想乘电梯。 B层有秘密实验室,禁止入内。然而,您已经有心情并决定连续乘坐 k 趟电梯。

让我们假设此时您位于 x 层(最初,您位于 a 层)。对于楼层之间的另一次行程,您选择某个编号为 y (y ≠ x) 的楼层,电梯将行驶到该楼层。由于您无法访问具有秘密实验室的楼层 b,因此您决定从当前楼层 x 到所选 y 的距离必须严格小于从当前楼层 x 到具有秘密实验室的楼层 b 的距离。形式上,这意味着必须满足以下不等式: |x - y| < |x - b|。电梯成功将您运送到 y 层后,您在记事本中记下数字 y。

你的任务是找出你可以写在笔记本上的不同数字序列的数量,作为电梯中 k 趟行程的结果。由于所求的行程数可能相当大,因此将该数字除以 1000000007 (109 + 7) 后求余数。

输入

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

输出

打印单个整数 - 将查找的序列数除以 1000000007 (109 + 7) 后的余数。

示例

输入 #1

5 2 4 1

输出 #1

2

输入 #2

5 2 4 2

输出 #2

2

输入 #3

5 3 4 1

输出 #3

0

注意

两个序列 p1, p2, ..., pk 和 q1, q2, ..., qk 是不同的,如果存在这样的整数 j (1 ≤ j ≤ k),则 pj ≠ qj。

样品注释:

1. 在第一次旅行后的第一个样本中,您要么在 1 楼,要么在 3 楼,因为 |1 - 2| < |2 - 4|和 |3 - 2| < |2 - 4|。
2. 在第二个样本中,有两个可能的序列:(1, 2); (1, 3)。第一次行程不能选择3层,因为这样就没有楼层可以作为第二次行程的楼层。
3. 在第三个示例中,没有搜索序列,因为您无法选择第一次行程的楼层。