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.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        InputStream is;
        OutputStream os;
        try {
            is = new FileInputStream("input.txt");
            os = new FileOutputStream("output.txt");
        } catch (FileNotFoundException e) {
            is = System.in;
            os = System.out;
        }
        InputReader in = new InputReader(is);
        PrintWriter out = new PrintWriter(os);
        Contest contest = new Contest(in, out);
        contest.solve();
        out.close();
    }

    static class Contest {
        InputReader in;
        PrintWriter out;
        public Contest(InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
        }

        int mod = 1000000007;

        int add(int a, int b) {
            int res = a + b;
            if(res >= mod)
                res -= mod;
            return res;
        }

        int sub(int a, int b) {
            int res = a - b;
            if(res < 0)
                res += mod;
            return res;
        }

        int mul(int a, int b) {
            return (int) ((long) a * b % mod);
        }

        int[][] f;
        int minv, maxv;

        int get_sum(int[] f, int l, int r, int ml, int dt)
        {
            int res = 0;
            for(int i = l; i <= r; i++) {
                res = add(res, mul(f[i - minv], ml));
                ml += dt;
            }
            return res;
        }

        public void solve() {
            int a, b, k, t;
            a = in.nextInt();
            b = in.nextInt();
            k = in.nextInt();
            t = in.nextInt();
            int dt = a - b;
            minv = dt - 2 * k * (t + 10);
            maxv = dt + 2 * k * (t + 10);
            f = new int[2][maxv - minv + 1];
            int cur = 0;
            f[cur][dt - minv] = 1;
            for(int it = 0; it < t; it++)
            {
                int ncur = cur ^ 1;
                int fr = dt - 2 * k * (it + 1);
                int to = dt + 2 * k * (it + 1);
                int l = get_sum(f[cur], fr - 2 * k, fr, 1, 0);
                int sl = get_sum(f[cur], fr - 2 * k, fr, 1, 1);
                int r = get_sum(f[cur], fr + 1, fr + 2 * k, 1, 0);
                int sr = get_sum(f[cur], fr + 1, fr + 2 * k, 2 * k, -1);
                int sm = add(sl, sr);
                for(int i = fr; i <= to; i++)
                {
                    f[ncur][i - minv] = sm;
                    sm = sub(sm, l);
                    l = sub(l, f[cur][i - 2 * k - minv]);
                    l = add(l, f[cur][i + 1 - minv]);
                    r = add(r, f[cur][i + 2 * k + 1 - minv]);
                    sm = add(sm, r);
                    r = sub(r, f[cur][i + 1 - minv]);
                }
                cur = ncur;
            }
            int ans = 0;
            for(int i = 1; i <= maxv; i++)
                ans = add(ans, f[cur][i - minv]);
            out.print(ans);
        }
    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer tk;
        public InputReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
            tk = null;
        }
        public String next() {
            if(tk == null || !tk.hasMoreTokens()) {
                try {
                    tk = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tk.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        public Long nextLong() {
            return Long.parseLong(next());
        }
    }
}
