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.
//package codeforces;

import java.io.*;
import java.util.*;

public final class TaskD
{
    public static void main(String[] args)
    {
        InputReader in = new InputReader(System.in);
        OutputWriter out = new OutputWriter(System.out);
        Solver solver = new Solver(in, out);

        solver.solve();

        in.close();
        out.flush();
        out.close();
    }

    static class Solver
    {
        static final long mod = (long) (1e9 + 7);
        int a, b, k, t;
        long[][] dpA, dpB;
        InputReader in;
        OutputWriter out;

        void solve()
        {
            a = in.nextInt();
            b = in.nextInt();
            k = in.nextInt();
            t = in.nextInt();
            a = k * t + a;
            b = k * t + b;

            int limit = Math.max(a, b) + k * t + 1;

            dpA = new long[t + 1][limit + 1];
            dpB = new long[t + 1][limit + 1];
            dpA[0][a] = 1;
            dpB[0][b] = 1;
            dpA[1][a - k] = 1;

            if (a + k + 1 <= limit)
                dpA[1][a + k + 1] = -1;

            dpB[1][b - k] = 1;

            if (b + k + 1 <= limit)
                dpB[1][b + k + 1] = -1;

            for (int i = 1; i <= t; i++)
            {
                for (int j = 0; j <= limit; j++)
                {
/*                    if (dpA[i][j] < 0)
                        System.out.println("^^^^ i : " + i + ", j : " + j);*/

                    dpA[i][j] += (j > 0 ? dpA[i][j - 1] : 0);
                    dpA[i][j] = CMath.mod(dpA[i][j], mod);

/*                    if (dpA[i][j] < 0)
                        System.out.println("i : " + i + ", j : " + j);*/

                    while (dpA[i][j] < 0)
                        dpA[i][j] += mod;

/*
                    if (dpA[i][j] < 0)
                    {
                        System.out.println("****** neg, i : " + i + ", j : " + j + ", prev : " + (dpA[i][j] -=
                                dpA[i][j - 1]));
                    }
*/

                    if (i < t && dpA[i][j] > 0)
                    {
                        dpA[i + 1][j - k] += dpA[i][j];
                        dpA[i + 1][j - k] = CMath.mod(dpA[i + 1][j - k], mod);

                        if (j + k + 1 <= limit)
                            dpA[i + 1][j + k + 1] -= dpA[i][j];
                    }
                }
            }

/*            for (int i = 0; i <= limit; i++)
                System.out.print(dpA[9][i] + " ");*/

            System.out.println();

/*            System.out.println("dpA :");

            for (int i = 0; i <= t; i++, System.out.println())
                for (int j = 0; j <= limit; j++)
                    System.out.print(dpA[i][j] + " ");*/

            for (int i = 1; i <= t; i++)
            {
                for (int j = 0; j <= limit; j++)
                {
                    dpB[i][j] += (j > 0 ? dpB[i][j - 1] : 0);
                    dpB[i][j] = CMath.mod(dpB[i][j], mod);

                    while (dpB[i][j] < 0)
                        dpB[i][j] += mod;

                    if (i < t && dpB[i][j] > 0)
                    {
                        dpB[i + 1][j - k] += dpB[i][j];
                        dpB[i + 1][j - k] = CMath.mod(dpB[i + 1][j - k], mod);

                        if (j + k + 1 <= limit)
                            dpB[i + 1][j + k + 1] -= dpB[i][j];
                    }
                }
            }

/*            System.out.println("dpB :");

            for (int i = 0; i <= t; i++, System.out.println())
                for (int j = 0; j <= limit; j++)
                    System.out.print(dpB[i][j] + " ");*/

            long[] pre = new long[limit + 1];

            pre[0] = dpB[t][0];

            for (int i = 1; i <= limit; i++)
            {
                pre[i] = pre[i - 1] + dpB[t][i];
                pre[i] = CMath.mod(pre[i], mod);
            }

//            long answer = dpA[t][0];

            long answer = 0;

            for (int i = 1; i <= limit; i++)
                if (dpA[t][i] > 0)
                    answer = CMath.mod(answer + CMath.mod(dpA[t][i] * pre[i - 1], mod), mod);

            out.println(answer);
        }

        public Solver(InputReader in, OutputWriter out)
        {
            this.in = in;
            this.out = out;
        }

    }

    static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream)
        {
            this.stream = stream;
        }

        public int read()
        {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars)
            {
                curChar = 0;
                try
                {
                    numChars = stream.read(buf);
                }
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt()
        {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-')
            {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public int[] nextIntArray(int arraySize)
        {
            int array[] = new int[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();

            return array;
        }

        public long nextLong()
        {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sign = 1;

            if (c == '-')
            {
                sign = -1;

                c = read();
            }

            long result = 0;

            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                result *= 10;
                result += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return result * sign;
        }

        public long[] nextLongArray(int arraySize)
        {
            long array[] = new long[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextLong();

            return array;
        }

        public float nextFloat() // problematic
        {
            float result, div;
            byte c;

            result = 0;
            div = 1;
            c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean isNegative = (c == '-');

            if (isNegative)
                c = (byte) read();

            do
            {
                result = result * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    result += (c - '0') / (div *= 10);

            if (isNegative)
                return -result;

            return result;
        }

        public double nextDouble() // not completely accurate
        {
            double ret = 0, div = 1;
            byte c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean neg = (c == '-');

            if (neg)
                c = (byte) read();

            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);

            if (neg)
                return -ret;

            return ret;
        }

        public String next()
        {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            StringBuilder res = new StringBuilder();

            do
            {
                res.appendCodePoint(c);

                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String nextLine()
        {
            int c = read();

            StringBuilder result = new StringBuilder();

            do
            {
                result.appendCodePoint(c);

                c = read();
            } while (!isNewLine(c));

            return result.toString();
        }

        public boolean isNewLine(int c)
        {
            return c == '\n';
        }

        public void close()
        {
            try
            {
                stream.close();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }

    }

    static class OutputWriter
    {
        private PrintWriter writer;

        public OutputWriter(OutputStream stream)
        {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                    stream)));
        }

        public OutputWriter(Writer writer)
        {
            this.writer = new PrintWriter(writer);
        }

        public void println(int x)
        {
            writer.println(x);
        }

        public void print(int x)
        {
            writer.print(x);
        }

        public void println(char x)
        {
            writer.println(x);
        }

        public void print(char x)
        {
            writer.print(x);
        }

        public void println(int array[], int size)
        {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(int array[], int size)
        {
            for (int i = 0; i < size; i++)
                print(array[i] + " ");
        }

        public void println(long x)
        {
            writer.println(x);
        }

        public void print(long x)
        {
            writer.print(x);
        }

        public void println(long array[], int size)
        {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(long array[], int size)
        {
            for (int i = 0; i < size; i++)
                print(array[i]);
        }

        public void println(float num)
        {
            writer.println(num);
        }

        public void print(float num)
        {
            writer.print(num);
        }

        public void println(double num)
        {
            writer.println(num);
        }

        public void print(double num)
        {
            writer.print(num);
        }

        public void println(String s)
        {
            writer.println(s);
        }

        public void print(String s)
        {
            writer.print(s);
        }

        public void println()
        {
            writer.println();
        }

        public void printSpace()
        {
            writer.print(" ");
        }

        public void printf(String format, Object args)
        {
            writer.printf(format, args);
        }

        public void flush()
        {
            writer.flush();
        }

        public void close()
        {
            writer.close();
        }

    }

    static class CMath
    {
        static long power(long number, long power)
        {
            if (number == 1 || number == 0 || power == 0)
                return 1;

            if (power == 1)
                return number;

            if (power % 2 == 0)
                return power(number * number, power / 2);
            else
                return power(number * number, power / 2) * number;
        }

        static long modPower(long number, long power, long mod)
        {
            if (number == 1 || number == 0 || power == 0)
                return 1;

            number = mod(number, mod);

            if (power == 1)
                return number;

            long square = mod(number * number, mod);

            if (power % 2 == 0)
                return modPower(square, power / 2, mod);
            else
                return mod(modPower(square, power / 2, mod) * number, mod);
        }

        static long moduloInverse(long number, long mod)
        {
            return modPower(number, mod - 2, mod);
        }

        static long mod(long number, long mod)
        {
            return number - (number / mod) * mod;
        }

        static int gcd(int a, int b)
        {
            if (b == 0)
                return a;
            else
                return gcd(b, a % b);
        }

    }

}
