• 문제 링크(http://211.229.66.5/30stair/worm/worm.php?pname=worm&stair=21)
  
• Dynamic Programming
  
• 벌레는 태어난지 a날부터 b날까지 매일 한마리의 벌레를 낳고 태어난지 d날째에 죽는다. N날이 지났을 때 벌레는 몇마리?
  
• 점화식 사용
  
  • N일의 개체수 = N-1일의 개체수(태어난 것 불포함) + N일에 태어난 수 - N-d일 태어난 수(오늘 죽는 수)
    
  • N일 태어난 수 = N일 출산 가능한 수 = N-1일 출산가능 + N일 성체가되는 수 - N일 출산불가시작개체 수
    
    • = N-1일 출산가능 + N-a일 태어난 수 - N-b일 태어난 수
      
• 주의
  
  • N일 태어난 수가 N일 출산 가능 수와 항상 같은가? -> 0번째날은 아님
    
    

//
//  21_worm.cpp
//  dovelet
//
//  Created by Jereneal Kim on 13. 7. 25..
//  Copyright (c) 2013년 Jereneal Kim. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

int arr[1000001]={0}; // n째 개체수
int arr2[1000001]={0}; // n째 출산가능수,태어난수
int main()
{
	int a,b,d,N,i;

	scanf("%d %d %d %d",&a,&b,&d,&N);
	
	arr2[0]=arr[0]=1;
	if(a==1){
		arr[1]=arr[0]+1;
		arr2[1]=1;
	}else{
		arr[1]=arr[0];
	}
	for(i=2;i<=N;i++){
		
		if(i>=a){
			if(i>=b){
				arr2[i]=arr2[i-1]+arr2[i-a]-arr2[i-b];
			}else{
				arr2[i]=arr2[i-1]+arr2[i-a];
			}
			if(i>=d){
				arr[i]=arr[i-1]+arr2[i]-arr2[i-d];
			}else{
				arr[i]=arr[i-1]+arr2[i];
			}
		}else{
			arr2[i]=arr2[i-1];
			arr[i]=arr[i-1];
		}
		
		if(arr[i]<0){
			arr[i]+=1000;
		}
		if(arr2[i]<0){
			arr2[i]+=1000;
		}
		arr[i]%=1000;
		arr2[i]%=1000;
		
	}

	printf("%d",arr[N]%1000);
	
    return 0;
}