짚신벌레

한 생물학자가 새로 발견한 짚신벌레의 번식 과정을 관찰한다. 이 종은 무성 생식을 하며, 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으로 나눈 나머지를 출력한다.