Memory 和他的朋友 Lexa 正在一场流行的电脑游戏中争夺更高的分数。内存从分数 a 开始,Lexa 从分数 b 开始。在一轮中,Memory 和 Lexa 都会获得 [ - k;k] 范围内的某个整数(即 - k、- k + 1、- k + 2、...、- 2、- 1、0、1、2、...、k - 1、k 中的一个整数)并将它们添加到当前分数中。游戏总共有 t 个回合。然而,Memory 和 Lexa 并不擅长这个游戏,因此它们总是在轮到时得到一个随机整数。
记忆想知道有多少种可能的游戏可以让他以严格高于 Lexa 的分数结束。如果至少在一轮中至少有一名玩家获得不同的分数,则两场比赛被认为是不同的。总共有 (2k + 1)2t 场比赛。由于答案可能非常大,因此您应该打印它模 109 + 7。请解决内存问题。
输入
输入的第一行也是唯一一行包含四个整数 a、b、k 和 t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100)——分别是 Memory 和 Lexa 的起始数量、数量 k 和圈数。
输出
在一行中打印满足模 1 000 000 007 (109 + 7) 条件的可能游戏数。
示例
输入 #1
1 2 2 1
输出 #1
6
输入 #2
1 1 1 2
输出 #2
31
输入 #3
2 12 3 1
输出 #3
0
注意
在第一个示例测试中,Memory 从 1 开始,Lexa 从 2 开始。如果 Lexa 选择 - 2,Memory 可以选择 0、1 或 2 获胜。如果 Lexa 选择 - 1,Memory 可以选择 1 或 2 获胜。如果Lexa选0,Memory可以选2获胜。如果 Lexa 选择 1 或 2,则 Memory 无法获胜。因此,内存获胜的可能游戏有 3 + 2 + 1 = 6 种。