짚신벌레
면접 대비시간 제한1초메모리 제한128 MB
개체가 특정 나이 구간에 매일 새끼를 낳고 정해진 나이에 죽는 규칙에 따라 번식할 때, N일째 살아있는 개체 수를 1000으로 나눈 나머지로 구합니다.
문제
한 생물학자가 새로 발견한 짚신벌레의 번식 과정을 관찰한다. 이 종은 무성 생식을 하며, 0일째에 새로 태어난 개체 한 마리를 수조에 넣는다.
각 개체는 태어난 뒤 지난 일수, 즉 나이에 따라 다음과 같이 행동한다.
- 나이가
a일이 되는 순간 성체가 된다. - 나이가
a이상b미만인 날마다 새 개체 한 마리를 낳는다. 성체가 되는 바로 그 날에도 한 마리를 낳는다. - 나이가
b일이 되는 순간부터는 더 이상 새 개체를 낳지 않는다. 따라서 한 개체는 평생b - a마리를 낳는다. - 나이가
d일이 되는 순간 죽어 수조에서 사라진다.
매일의 성장, 출산, 사망이 반영된 뒤 그 날 수조에 살아 있는 개체 수를 센다. 번식 정보 a, b, d와 날짜 N이 주어질 때, N일째 되는 날 살아 있는 개체 수를 구하시오.
입력
첫째 줄에 네 정수 a, b, d, N이 공백으로 구분되어 주어진다.
0 < a < b < d <= 10,000, 1 <= N <= 1,000,000
출력
새로 태어난 개체 한 마리를 넣은 뒤 N일째 되는 날, 수조에 살아 있는 개체 수를 1000으로 나눈 나머지를 출력한다.