#include <stdio.h>
//#include <stdlib.h>


int num_count(int a, int b, int d, int n);
int main(void)
{
	int a, b, d, n;
	int num;
	//a=성체가 되는 날  b=더이상 개체를 만들어내지 않는 날 d=죽는 날 n=날짜

	scanf(" %d %d %d %d", &a, &b, &d, &n);

	num=num_count(a, b, d, n);

	printf("%d", num%1000);

	return 0;
}
int num_count(int a, int b, int d, int n)
{
	int cnt=0, t[10001]={0}, temp;
	int i, j;

	t[0]=1;
	cnt+=1;

	for(i=1; i<=n; i++)
	{
		temp=t[0]%1000;

		if(i!=1)
			t[0]=0;

		for(j=d; j>=b; j--) //더이싱 새 개체를 만들어 내지 않는 기간부터 죽는 날짜까지
		{
			t[j]=t[j-1]%1000;
		}
		cnt-=t[d]; //죽은 개체 수만큼 빼주기

		for(j=b-1; j>=a; j--) //성체가 되어 새 개체를 만들어내기 시작하는 구간
		{
			if(j!=1)
				t[j]=t[j-1]%1000;
			else
				t[j]=temp;

			t[0]+=t[j]%1000;
			cnt+=t[j]; //새로 태어난 개체 수만큼 더하기
		}

		for(j=a-1; j>1; j--) //성체가 되기 전
		{
			t[j]=t[j-1]%1000;
		}

		t[1]=temp;
		if(i==1)
			t[0]-=temp;

		//for(j=0; j<=d; j++)
		//	t[j]%=1000;
		cnt%=1000;
		/*printf("%3d 일째: ", i); 
		for(j=0; j<=d; j++)
		{
			 printf("[%d]- %2.0f    ", j, t[j]);
		}
		printf("\n");
		printf("cnt=%.0f\n", cnt);
		system("pause");*/
	}

//	while(cnt>1000) cnt=cnt-1000;

	return cnt;
}