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.util.*;
public class Main
{
public static void main(String[] args)throws java.lang.Exception
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);

int a1,b1,k,t,ka,kb,center,i,lim,span,left,right,t1;
long sum1,val;

int mod=1000000007;

StringTokenizer st=new StringTokenizer(in.readLine().trim());

a1=Integer.parseInt(st.nextToken());
b1=Integer.parseInt(st.nextToken());
k=Integer.parseInt(st.nextToken());
t=Integer.parseInt(st.nextToken());


lim=(2*(k*t)+1);
span=2*k+1;
int[] a=new int[lim];
int[] sum=new int[lim+1];
int[] new_sum=new int[lim+1];
center=k*t;                       //  cnt of 0 is stored here 



for(i=center-k;i<=center+k;i++)
    a[i]=1;



for(i=lim-1;i>=0;i--)
{
    sum[i]=(sum[i+1]+a[i])%mod;
    new_sum[i]=sum[i];
}


/*
for(i=0;i<=lim;i++)
    {
        out.println("sum["+i+"] = "+sum[i]);
    }
    out.println();
*/


for(t1=1;t1<t;t1++)
{

    for(i=0;i<lim;i++)
    {
        left=Math.max(0,i-k);
        right=Math.min(i+k,lim-1);

        new_sum[i]=sum[left]-sum[right+1];
        if(new_sum[i]<0)
            new_sum[i]+=mod;
    }


    for(i=lim-1;i>=0;i--)
    {
    sum[i]=(sum[i+1]+new_sum[i])%mod;
    }


    /*
    for(i=0;i<=lim;i++)
    {
        out.println("sum["+i+"] = "+sum[i]);
    }
    out.println();
    */
}






kb=-1*(k*t);

sum1=0L;

for(i=0;i<lim;i++)
{
    ka=-1*(a1-(b1+kb+1));

    //out.println(ka);

    ka=Math.max(-1*(k*t),ka);
    ka=Math.min((k*t)+1,ka);

    //out.println("  "+ka);

    if(t>1)
        val=(long)new_sum[kb+center];
    else
        val=(long)a[kb+center];

    if(ka>=-1*(k*t) && ka<=(k*t))
    {
        val*=sum[ka+center];
        val%=mod;
    }
    else
    {
        val=0L;
    }


    sum1+=val;
    sum1%=mod;

    kb++;
}



out.println(sum1);


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