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.math.*;
import java.io.*;
import java.util.*;
public class C712D{
   public static long[] cAr, div;
   public static int N,M;
   public static int[] numCycle;
   public static Map<Integer,Set<Integer>> map;
   public static long MOD = 1000000007;
   public static void main(String[] args) throws IOException{
      InputReader in=new InputReader(new InputStreamReader(System.in));
      PrintWriter out=new PrintWriter(new BufferedOutputStream(System.out));
      int[] ar1=in.nextIntAr();
      int A=ar1[0];
      int B=ar1[1];
      int K=ar1[2];
      int T=ar1[3];
      int total=(2*K)*T+1;
      long[] ar=new long[total];
      ar[0]=1;
      long[] tempAr=new long[total];
      for(int x=0;x<T;x++) {
         int low=-2*K-1;
         long sum=0;
         for(int y=0;y<total;y++){
            sum+=ar[y];
            if(low>=0) sum-=ar[low];
            low++;
            sum=sum%MOD;
            tempAr[y]=sum;
         }
         for(int y=0;y<total;y++)
            ar[y]=tempAr[y];
      }
      int C=A-B-1;
      long sum=0;
      long cSum=0;
      for(int x=0;x<C;x++)
         cSum=(cSum+ar[x])%MOD;
      for(int x=0;x<total;x++) {
         if(0<=x+C && x+C<total){
            cSum=(cSum+ar[x+C])%MOD;
         }
         sum=(sum+(cSum*ar[x])%MOD)%MOD;
      }
      if(A-B>(2*K)*T) {
         sum=pow(2*K+1,2*T);
      }
      out.println(sum);
      out.close();
   }
   
   public static void setUpChoose(int t){
      cAr=new long[t+1];
      div=new long[t+1];
      cAr[0]=1;
      div[0]=1;
      
      for(int x=1;x<=t;x++){
         cAr[x]=(x*cAr[x-1])%(MOD);
         div[x]=pow(cAr[x],MOD-2);} 
   }
   
   public static long choose(int x,int y){
      long a=cAr[x+y];
      long b=div[x];
      long c=div[y];
      a=(a*b)%MOD;
      a=(a*c)%MOD;
      return a;
   }
   
   public static long pow(long a,long b){
      if(b==1) 
         return a;
      long c=b/2;
      long temp=pow(a,c)%MOD;
      temp=(temp*temp)%MOD;
      if(b%2==1) temp=temp*a;
      return temp%MOD;
   }
}

class InputReader{
   private BufferedReader br;
   public InputReader(InputStreamReader in){
      br=new BufferedReader(in);
   }
   public int nextInt(){
      try{
         return Integer.parseInt(br.readLine());}
      catch(IOException e){throw new InputMismatchException();}
   }
   public int[] nextIntAr(){
      try{
         String[] s=br.readLine().split(" ");
         int[] ret=new int[s.length];
         for(int x=0;x<s.length;x++)
            ret[x]=Integer.parseInt(s[x]);
         return ret;}
         
      catch(IOException e){throw new InputMismatchException();}
   }
   
   public long nextLong(){
      try{
         return Long.parseLong(br.readLine());}
      catch(IOException e){throw new InputMismatchException();}
   }
   public long[] nextLongAr(){
      try{
         String[] s=br.readLine().split(" ");
         long[] ret=new long[s.length];
         for(int x=0;x<s.length;x++)
            ret[x]=Long.parseLong(s[x]);
         return ret;}
         
      catch(IOException e){throw new InputMismatchException();}
   }
   
   public String[] nextStringAr(){
      try{
         return br.readLine().split(" ");}
         
      catch(IOException e){throw new InputMismatchException();}
   }
   
   public String nextString(){
      try{
         return br.readLine();}
         
      catch(IOException e){throw new InputMismatchException();}
   }
}
   
class Pair implements Comparable<Pair>{
   long a;
   long b;
   
   public Pair(long ma, long mb){
      a = ma;
      b = mb;
   }
   
   public int compareTo(Pair o){
      if(a == o.a){
         if(b==o.b) 
            return 0;
         return b<o.b?-1:1;
      }
      return a<o.a?-1:1;
   }
}