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 (2k + 1)2t games in total. Since the answer can be very large, you should print it modulo 109 + 7. Please solve this problem for Memory.

Input

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.

Output

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

Examples

Input

1 2 2 1


Output

6


Input

1 1 1 2


Output

31


Input

2 12 3 1


Output

0

Note

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.
#include <bits/stdc++.h>
using namespace std;
long long int PuntA[2][1001000];
long long int PuntB[2][1001000];
long long int sumaA[2][1001000];
long long int sumaB[2][1001000];
long long int MOD = (long long int)(1e9 + 7);
int main() {
  int a, b, k, t;
  cin >> a >> b >> k >> t;
  PuntA[0][a + k * t] = 1;
  PuntB[0][b + k * t] = 1;
  sumaA[0][a] = 0;
  for (int p = (a + 1); p < (a + 2 * k * t + 1); p++)
    sumaA[0][p] = (sumaA[0][p - 1] + PuntA[0][p]) % MOD;
  for (int i = 1; i <= t; i++) {
    int ant, cur;
    if (i % 2 == 0) {
      ant = 1;
      cur = 0;
    } else {
      ant = 0;
      cur = 1;
    }
    for (int p = (a); p < (a + 2 * k * t + 1); p++) {
      PuntA[cur][p] = (sumaA[ant][min(p + k, a + 2 * k * t)] -
                       sumaA[ant][max(p - k - 1, a - 1)]) %
                      MOD;
      if (PuntA[cur][p] < 0) PuntA[cur][p] += MOD;
      sumaA[cur][p] = (sumaA[cur][p - 1] + PuntA[cur][p]) % MOD;
    }
  }
  sumaB[0][b] = 0;
  for (int p = (b + 1); p < (b + 2 * k * t + 1); p++)
    sumaB[0][p] = (sumaB[0][p - 1] + PuntB[0][p]) % MOD;
  for (int i = 1; i <= t; i++) {
    int ant, cur;
    if (i % 2 == 0) {
      ant = 1;
      cur = 0;
    } else {
      ant = 0;
      cur = 1;
    }
    for (int p = (b); p < (b + 2 * k * t + 1); p++) {
      PuntB[cur][p] = (sumaB[ant][min(p + k, b + 2 * k * t)] -
                       sumaB[ant][max(p - k - 1, b - 1)]) %
                      MOD;
      if (PuntB[cur][p] < 0) PuntB[cur][p] += MOD;
      sumaB[cur][p] = (sumaB[cur][p - 1] + PuntB[cur][p]) % MOD;
    }
  }
  long long int ans = 0;
  long long int sumB = 0;
  int p1 = a;
  int p2 = b;
  while (p1 <= a + 2 * k * t) {
    while (p2 < p1) {
      sumB = (sumB + PuntB[t & 1][p2]) % MOD;
      p2++;
    }
    ans = (ans + sumB * PuntA[t & 1][p1]) % MOD;
    p1++;
  }
  cout << ans << endl;
  return 0;
}
