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;
template <typename Int>
Int gcd(Int a, Int b) {
  while (a != 0) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}
template <typename Int, typename RInt = Int>
Int lcm(Int a, Int b) {
  return a / gcd(a, b) * static_cast<RInt>(b);
}
template <typename Int, typename XInt>
Int extended_gcd(Int a, Int b, XInt &x, XInt &y) {
  static_assert(std::numeric_limits<XInt>::is_signed, "x, y must be signed");
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  Int g = extended_gcd(b, a % b, y, x);
  y -= (a / b) * x;
  return g;
}
template <typename Int, typename TInt = int64_t>
Int mul_mod(Int a, Int b, Int m) {
  TInt p = a;
  p = (p * b) % m;
  return p;
}
template <typename Int, typename PInt, typename TInt = int64_t>
Int pow_mod(Int a, PInt p, Int m) {
  Int r;
  a %= m;
  for (r = 1; p; p >>= 1) {
    if (p & 1) r = mul_mod(r, a, m);
    a = mul_mod(a, a, m);
  }
  return r;
}
template <typename Int, typename XInt = typename std::make_signed<Int>::type>
Int inv_mod(Int a, Int m) {
  XInt x, y;
  extended_gcd(a, m, x, y);
  if (x < 0) return x + m;
  return x;
}
template <typename Int>
Int div_pos_r(Int a, Int b, Int &r) {
  Int q = a / b;
  r = a % b;
  if (r < 0) {
    if (b < 0)
      q += 1, r -= b;
    else
      q -= 1, r += b;
  }
  return q;
}
template <typename Int, typename TInt = int64_t>
TInt crt2(Int a1, Int m1, Int a2, Int m2) {
  Int k1, k2;
  Int g = extended_gcd(m1, m2, k1, k2);
  Int r1, r2;
  a1 = div_pos_r(a1, g, r1);
  a2 = div_pos_r(a2, g, r2);
  if (r1 != r2) throw 0;
  m1 /= g;
  m2 /= g;
  TInt m12 = static_cast<TInt>(m1) * m2;
  return (static_cast<TInt>(a2) * k1 % m2 * m1 +
          static_cast<TInt>(a1) * k2 % m1 * m2) %
             m12 * g +
         r1;
}
template <typename Int>
Int counting(Int L, Int R, Int x0, Int dx) {
  Int tmp;
  return div_pos_r(R - x0, dx, tmp) - div_pos_r(L - 1 - x0, dx, tmp);
}
template <typename Int>
Int crtn(const std::vector<Int> &as, const std::vector<Int> &ms) {
  Int r = 1;
  Int m = 1;
  for (int i = 0; i < as.size(); ++i) {
    r = crt2(r, m, as[i], ms[i]);
    m *= ms[i];
  }
  return r;
}
template <typename Int>
Int factorial_exp(Int n, Int p) {
  Int r = 0;
  while (n) {
    n = n / p;
    r += n;
  }
  return r;
}
template <typename Int>
std::pair<Int, bool> log(Int n, Int b) {
  if (n <= 0) return {-1, true};
  Int ans = 0;
  bool frac = false;
  while (n >= b) {
    frac = frac || (n % b != 0);
    ans += 1;
    n /= b;
  }
  if (n != 1) frac = true;
  return {ans, frac};
}
struct int_iterator {
  int i;
  explicit int_iterator(int i = 0) : i(i) {}
  int operator*() const { return i; }
  int_iterator &operator++() {
    ++i;
    return *this;
  }
  bool operator==(const int_iterator &that) const { return i == that.i; }
  bool operator!=(const int_iterator &that) const { return !(*this == that); }
};
struct range {
  int b, e;
  range(int bp, int ep) : b(bp), e(ep) {
    if (e < b) e = b;
  }
  range(int e) : b(0), e(e) {}
  int_iterator begin() const { return int_iterator(b); }
  int_iterator end() const { return int_iterator(e); }
};
range nrange(int n) { return range(1, n + 1); }
range inrange(int b, int e) { return range(b, e + 1); }
template <typename T>
T &chmax(T &m, const T &v) {
  if (v > m) m = v;
  return m;
}
template <typename T>
T &chmin(T &m, const T &v) {
  if (v < m) m = v;
  return m;
}
template <typename T>
struct pos_checker {
  static bool check(const T &v) { return v >= 0; }
};
template <typename T, typename Checker = pos_checker<T> >
T &chmax_s(T &m, const T &v) {
  if (!Checker::check(v)) return m;
  if (!Checker::check(m)) return m = v;
  return chmax(m, v);
}
template <typename T, typename Checker = pos_checker<T> >
T &chmin_s(T &m, const T &v) {
  if (!Checker::check(v)) return m;
  if (!Checker::check(m)) return m = v;
  return chmin(m, v);
}
const int MOD = 1000000007;
vector<int> C(int k, int t) {
  vector<int> cur = {1};
  for (int i : range(t)) {
    vector<int> next(cur.size() + k - 1);
    int v = 0;
    for (int j : range(next.size())) {
      if (j < cur.size()) v = (v + cur[j]) % MOD;
      if (j - k >= 0) v = ((v - cur[j - k]) % MOD + MOD) % MOD;
      next[j] = v;
    }
    swap(cur, next);
  }
  return cur;
}
vector<int> acc(vector<int> v) {
  vector<int> r;
  int x = 0;
  for (int c : v) {
    x = (x + c) % MOD;
    r.push_back(x);
  }
  return r;
}
int main() {
  int a, b, k, t;
  cin >> a >> b >> k >> t;
  vector<int> cnt = C(2 * k + 1, t);
  vector<int> sum = acc(cnt);
  int ans = 0;
  for (int i : range(cnt.size())) {
    int s = a + i - b - 1;
    if (s < 0)
      continue;
    else if (s >= cnt.size())
      ans = (ans + mul_mod(cnt[i], sum.back(), MOD)) % MOD;
    else
      ans = (ans + mul_mod(cnt[i], sum[s], MOD)) % MOD;
  }
  cout << ans << endl;
  return 0;
}
