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 codeforeces370;


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


public class q1{
	static int mod=(int)(1e9+7);
	public static void main(String[] ags)
	{
		InputReader in=new InputReader(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		//int n=in.nextInt();
		//int[] a=readint(in,n);
		int a=in.nextInt();
		int b=in.nextInt();
		int k=in.nextInt();
		int t=in.nextInt();
		long[][] dp=new long[2*k*t+1001][t+1];
		int offset=k*t;
		dp[offset][0]=1;
		for(int i=1;i<=t;i++)
		{
			
			
				
				for(int j=-(i-1)*k;j<=(i-1)*k;j++)
				{
				
					dp[j+offset-k][i]+=dp[j+offset][i-1];
					dp[j+offset-k][i]%=mod;
				}
				
				
				long total=0;
				long[] pre=new long[2*k*t+1000];
				
				for(int j=-i*k;j<=i*k;j++)
				{
					
					total+=dp[j+offset][i];
					//System.out.println(j+offset);
					pre[j+offset]=total;
					total%=mod;
					dp[j+offset][i]=total;
					if(j-(2*k+1)+offset>=0)
					{
						dp[j+offset][i]-=pre[j-(2*k+1)+offset];
						dp[j+offset][i]%=mod;
						if(dp[j+offset][i]<0)
						{
							dp[j+offset][i]+=mod;
						}
					}
					
					
					
				}
				
				
				
		}
		long[] presum=new long[2*k*t+1001];
		
		for(int i=-k*t;i<=k*t;i++)
		{
			presum[i+offset]=dp[i+offset][t];
			presum[i+offset]%=mod;
			if(i-1+offset>=0)
			{
				presum[i+offset]+=presum[i+offset-1];
			}
			presum[i+offset]%=mod;
		}
		long ans=0;
		
		for(int i=-k*t;i<=k*t;i++)
		{
		
		int l=-k*t;
		int r=k*t;
		if(a+i<=b+l)
		{
			continue;
		}
		int mid=-1;
		while(l<=r)
		{
			int mm=(l+r)>>1;
			if(l==r || r==l+1)
			{
				if(a+i>b+r)
				{
					mid=r;
					break;
				}
				mid=l;
				break;
			}
			if(a+i>b+mm)
			{
				l=mm;
			}
			else
			{
				r=mm;
			}
			
		}
		//System.out.println("mid is "+mid+"  for "+i);
		//System.out.println("presum mid is "+presum[mid+offset]+" dp is "+dp[i+offset][t]);
		long tt=presum[mid+offset]*dp[i+offset][t];
		tt%=mod;
		ans+=tt;
		ans%=mod;
		}
		System.out.println(ans%mod);
		
		
		pw.close();
	}
	public static int[] readint(InputReader in,int n)
	{
		int[] a=new int[n];
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextInt();
		}
		return a;
	}
	public static long[] readlong(InputReader in,int n)
	{
		long[] a=new long[n];
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextLong();
		}
		return a;
	}
	public static void addhm(HashMap<Integer,Integer> hm,int k)
	{
		int cc=0;
		if(hm.containsKey(k))
		{
			cc=hm.get(k);
		}
		hm.put(k, cc+1);
	}
	public static void removehm(HashMap<Integer,Integer> hm,int k)
	{
		int cc=hm.get(k);
		if(cc==1)
		{
			hm.remove(k);
		}
		else
		{
			hm.put(k,cc-1);
		}
	}
	
	static class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar;
		private int snumChars;
		private SpaceCharFilter filter;

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

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}

			int res = 0;

			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}

			long res = 0;

			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

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

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

}
