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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class D {

    private static final boolean TEST_CASES = false;
    private static final int mod = 1000000007;


    private static class Solver {
        void solve(int testCaseNo) {

		int a, b, k, t;
		a = IO.nextInt();
		b = IO.nextInt();
		k = IO.nextInt();
		t = IO.nextInt();

		int maxn = Math.max(a,b) + 2 * k * t;

		int[][] s = new int[maxn+1][2];
		s[0][0] = 1;
		int cur = 0;
		for (int i = 1; i <= t; ++i) {
			cur = 1-cur;
			int id = -1 - 2*k;
			for (int j = 0; j <= maxn; ++j) {
				s[j][cur] = s[j][1-cur];
				if (j > 0) s[j][cur] += s[j-1][cur];
				if (s[j][cur] >= mod) s[j][cur] -= mod;
				if (id >= 0) s[j][cur] -= s[id][1-cur];
				id++;
				if (s[j][cur] < 0) s[j][cur] += mod;
				else if (s[j][cur] >= mod) s[j][cur] -= mod;

			}
		}


		// compute number of ways
		int[] prec = new int[maxn+1];
		for (int i = b; i <= maxn; ++i) {
			prec[i] = s[i-b][cur];
			if (i > 0) prec[i] += prec[i-1];
			if (prec[i] >= mod) prec[i] -= mod;
		}

		int res = 0;
		for (int i = a; i <= maxn; ++i) {
			long r = (long)s[i-a][cur] * prec[i-1];
			r = r%mod;
			res += (int)r;
			if (res >= mod) res -= mod;
		}

		IO.writer.println(res);
	}
	

    }

    private static class IO {

        private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static final PrintWriter writer = new PrintWriter(System.out);

        private static StringTokenizer tokenizer = null;

        static String nextToken() {
            checkTokenizer();
            return tokenizer.nextToken();
        }

        static int nextInt() {
            return Integer.parseInt(nextToken());
        }

        static void close() {
            writer.flush();
        }

        private static boolean isTokenizerEmpty() {
            return tokenizer == null || !tokenizer.hasMoreTokens();
        }

        private static void checkTokenizer() {
            while (isTokenizerEmpty()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }
    }

    private static void go() {
        int testCases = TEST_CASES ? IO.nextInt() : 1;

        Solver solver = new Solver();
        for (int testCase = 0; testCase < testCases; testCase++) {
            solver.solve(testCase);
        }
    }

    public static void main(String[] args) {
        try {
            go();
        } finally {
            IO.close();
        }
    }
}
