CF712D.Memory and Scores

Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score a and Lexa starts with score b. In a single turn, both Memory and Lexa get some integer in the range [ - k;k] (i.e. one integer among  - k,  - k + 1,  - k + 2, ...,  - 2,  - 1, 0, 1, 2, ..., k - 1, k) and add them to their current scores. The game has exactly t turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.

Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are (2_k_ + 1)2_t_ games in total. Since the answer can be very large, you should print it modulo 109 + 7. Please solve this problem for Memory.

Memory 和他的朋友 Lexa 正在一款流行的电脑游戏中竞争，以获得更高的分数。Memory 的初始分数为 $a$，Lexa 的初始分数为 $b$。在每一轮中，Memory 和 Lexa 各自独立地获得一个范围在 $[-k,\,k]$ 内的整数（即从 $-k,\,-k+1,\,-k+2,\,\dots,\,-2,\,-1,\,0,\,1,\,2,\,\dots,\,k-1,\,k$ 中任取一个整数），并将其加到各自的当前分数上。游戏共进行恰好 $t$ 轮。然而，Memory 和 Lexa 都不擅长这款游戏，因此他们在每一轮中总是随机获得一个整数。

Memory 想知道：有多少种可能的游戏过程，使得他在游戏结束时的分数严格高于 Lexa 的分数？若存在至少一轮中，至少有一名玩家获得的分数不同，则认为这两个游戏过程是不同的。总共有 $(2k+1)^{2t}$ 种可能的游戏过程。由于答案可能非常大，请你将结果对 $10^9 + 7$ 取模后输出。请帮 Memory 解决这个问题。

The first and only line of input contains the four integers a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) — the amount Memory and Lexa start with, the number k, and the number of turns respectively.

输入仅有一行，包含四个整数 $a$、$b$、$k$ 和 $t$（$1 ≤ a, b ≤ 100$，$1 ≤ k ≤ 1000$，$1 ≤ t ≤ 100$）——分别表示 Memory 和 Lexa 的初始分数、数字 $k$ 以及回合数。

Print the number of possible games satisfying the conditions modulo 1 000 000 007 (109 + 7) in one line.

在一行中输出满足条件的游戏数量对 1 000 000 007（即 $10^9 + 7$）取模的结果。

In the first sample test, Memory starts with 1 and Lexa starts with 2. If Lexa picks  - 2, Memory can pick 0, 1, or 2 to win. If Lexa picks  - 1, Memory can pick 1 or 2 to win. If Lexa picks 0, Memory can pick 2 to win. If Lexa picks 1 or 2, Memory cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which Memory wins.

在第一个样例测试中，Memory 的初始分数为 $1$，Lexa 的初始分数为 $2$。若 Lexa 选择 $-2$，则 Memory 可选择 $0$、$1$ 或 $2$ 获胜；若 Lexa 选择 $-1$，则 Memory 可选择 $1$ 或 $2$ 获胜；若 Lexa 选择 $0$，则 Memory 可选择 $2$ 获胜；若 Lexa 选择 $1$ 或 $2$，则 Memory 无法获胜。因此，Memory 获胜的可能游戏总数为 $3 + 2 + 1 = 6$。