← 返回题目列表

Codeforces · 712/D

D. 记忆和分数

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

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 种。