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

public class A {
    static class Node implements Comparable<Node>{
        int x;
        long w;
        int id;

        public Node(int x,long w,int id){
           this.x=x;
           this.w=w;
           this.id=id;
        }
        public int compareTo(Node c){
            int i=Long.compare(this.w,c.w);
          return i;

        }
        @Override
        public boolean equals(Object o){
            if(o instanceof Node){
                Node c = (Node)o;
                return true;
            }
            return false;
        }
    }

    //public static PrintWriter pw;
    public static PrintWriter pw = new PrintWriter(System.out);

    public static void solve() throws IOException {
//	pw=new PrintWriter(new FileWriter("C:\\Users\\shree\\Downloads\\small_output_in"));
        FastReader sc = new FastReader();
        int a=sc.I(); int b=sc.I();  k=sc.I(); int n=sc.I();
        int MX=200001;
        dp1=new long[2][2*MX+1];
        dp2=new long[2][2*MX+1];

        dp1[0][a+MX]=1;
        dp2[0][b+MX]=1;
        int mx=Math.max(a,b)+k*n+MX;
        int mn=Math.min(a,b)-k*n+MX;

        for(int i=1;i<=n;i++) {
             for(int j=mn;j<=mx;j++){



                     dp1[i%2][j - k] += dp1[(i - 1)%2][j];
                     dp1[i%2][j + k + 1] -= dp1[(i - 1)%2][j];

                     dp2[i%2][j - k] += dp2[(i - 1)%2][j];
                     dp2[i%2][j + k + 1] -= dp2[(i - 1)%2][j];
                     dp1[(i-1)%2][j]=0;
                     dp2[(i-1)%2][j]=0;

             }
             for(int j=mn;j<=mx;j++){
                 dp1[i%2][j]=(dp1[i%2][j]+dp1[i%2][j-1])%M;
                 dp2[i%2][j]=(dp2[i%2][j]+dp2[i%2][j-1])%M;
             }


        }
        long ans=0;

        long sum2[]=new long[2*MX+1];

        for(int i=mn;i<=mx;i++){
            sum2[i]=(sum2[i-1]+dp2[n%2][i])%M;
        }
        for(int i=mn;i<=mx;i++){
            ans=(ans+(dp1[n%2][i]*sum2[i-1])%M)%M;
          //  pw.println(dp1[n][i]+" "+sum2[i-1]);



        }
        pw.println(ans);

        pw.close();


    }
    static long dp1[][];
    static long dp2[][];
    static int k;

    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                try {

                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();

    }

    static BufferedReader br;
    static long M = (long) 1e9 + 7;

    static class FastReader {

        StringTokenizer st;

        public FastReader() throws FileNotFoundException {
            //br=new BufferedReader(new FileReader("C:\\Users\\shree\\Downloads\\B-small-practice.in"));
            br = new BufferedReader(new InputStreamReader(System.in));

        }

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

        int I() {
            return Integer.parseInt(next());
        }

        long L() {
            return Long.parseLong(next());
        }

        double D() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public boolean hasNext() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return false;
                }
                st = new StringTokenizer(s);
            }
            return true;
        }

    }
}