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.
import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    static final String FILE = "";

    public static final int MAXN = 3 * 1000 * 100 + 1000;
    //public static final int MAXN = 1000;
    public static final int MOD = (int)1e9 + 7;

    int a, b, k, t;
    int[][] canA;
    int[][] canB;
    int[] realA;
    int[] realB;

    int getA(int turn, int from, int to) {
        int cur;
        if (to < MAXN)
            cur = canA[turn][to];
        else
            cur = canA[turn][MAXN - 1];
        if (from > 0) {
            cur -= canA[turn][from - 1];
            if (cur < 0)
                cur += MOD;
        }
        return cur;
    }

    int getB(int turn, int from, int to) {
        int cur;
        if (to < MAXN)
            cur = canB[turn][to];
        else
            cur = canB[turn][MAXN - 1];
        if (from > 0) {
            cur -= canB[turn][from - 1];
            if (cur < 0)
                cur += MOD;
        }
        return cur;
    }

    void solve() {
        a = in.nextInt();
        b = in.nextInt();
        k = in.nextInt();
        t = in.nextInt();
        canA = new int[2][MAXN];
        canB = new int[2][MAXN];
        realA = new int[MAXN];
        realB = new int[MAXN];

        for (int i = a + MAXN / 2; i < MAXN; i++)
            canA[0][i] = 1;
        for (int turn = 1; turn <= t; turn++) {
            int ind = turn % 2;
            for (int i = 0; i < MAXN; i++) {
                canA[ind][i] = getA(1 - ind, i - k, i + k);
                if (turn == t)
                    realA[i] = canA[ind][i];
                if (i > 0) {
                    canA[ind][i] += canA[ind][i - 1];
                    if (canA[ind][i] >= MOD)
                        canA[ind][i] -= MOD;
                }
            }
        }

        for (int i = b + MAXN / 2; i < MAXN; i++)
            canB[0][i] = 1;
        for (int turn = 1; turn <= t; turn++) {
            int ind = turn % 2;
            for (int i = 0; i < MAXN; i++) {
                canB[ind][i] = getB(1 - ind, i - k, i + k);
                if (turn == t)
                    realB[i] = canB[ind][i];
                if (i > 0) {
                    canB[ind][i] += canB[ind][i - 1];
                    if (canB[ind][i] >= MOD)
                        canB[ind][i] -= MOD;
                }
            }
        }

        for (int i = 1; i < MAXN; i++) {
            realB[i] += realB[i - 1];
            if (realB[i] >= MOD)
                realB[i] -= MOD;
        }

        long ans = 0;
        for (int i = 1; i < MAXN; i++) {
            ans += (long) (realA[i]) * (long) (realB[i - 1]);
            ans %= MOD;
        }

        out.println(ans);
    }

    public void run() {
        if (FILE.equals("")) {
            in = new FastScanner(System.in);
            out = new PrintWriter(System.out);
        } else {
            try {
                in = new FastScanner(new FileInputStream(FILE +
                        ".in"));
                out = new PrintWriter(new FileOutputStream(FILE +
                        ".out"));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        solve();
        out.close();
    }

    public static void main(String[] args) {
        (new Main()).run();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }
    }

}