想象一下,您在一栋恰好有 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. 在第三个示例中,没有搜索序列,因为您无法选择第一次行程的楼层。