짚신벌레

한 생물학자가 새로 발견된 짚신벌레 종의 생태에 대해 연구하고 있다. 매우 번식력이 강하다고 알려진 이 종은 아래와 같은 특징을 가지고 있다.

무성 생식을 한다.

• 태어난 이후 $a$일째 되는 날 성체가 된다.
• 성체가 된 날부터 매일 한 마리씩 새로운 개체를 만들어낸다. 즉, 성체가 되자마자 첫 개체를 만들어내고, 그 이후로 하루가 지날 때마다 새로운 개체를 하나씩 만들어낸다. 새로운 개체 역시 태어난 이후로 $a$일째 되는 날부터 성체가 되어 새로운 개체를 만든다.
• 태어난 이후로 $b$일째 되는 순간부터는 새로운 개체를 더 이상 만들지 않는다. 태어난 지 $a$일째 날부터 $b$일째 되는 날의 전날까지 새로운 개체를 만들어내므로 일생동안 총 $(b - a)$마리의 개체를 만들어낸다.
• 태어난 이후로 $d$일째 되는 순간 죽는다.

아래는 $a = 2$, $b = 4$, $d = 6$일 때 수조에 새로 태어난 짚신벌레 한 마리를 넣고 매일 관찰한 결과를 기록한 것이다. 괄호 안의 숫자들은 수조 안의 짚신벌레들이 각각 태어난 이후 며칠이 되었는지를 나타내는 정수이다.

• 태어난 날: $(0)$ — 새로운 개체를 집어넣음
• 1일째 되는 날: $(1)$ — 짚신벌레가 자람
• 2일째 되는 날: $(2, 0)$ — 짚신벌레가 태어난 지 2일째가 되므로 성체가 되고 새 개체를 만들어 냄
• 3일째 되는 날: $(3, 1, 0)$ — 2일째 성체가 된 짚신벌레가 오늘도 새 개체를 하나 만들어 냄
• 4일째 되는 날: $(4, 2, 1, 0)$ — 2일째 되는 날 만들어진 짚신벌레가 새로운 개체를 만들어 냄 (처음에 넣은 짚신벌레는 새 개체를 만들어내지 못함)
• 5일째 되는 날: $(5, 3, 2, 1, 0, 0)$
• 6일째 되는 날: $(4, 3, 2, 1, 1, 0, 0)$ — 처음에 넣은 개체는 죽는다.

6일째 되는 날 수조 안에 살아있는 짚신벌레는 총 7마리가 된다.

짚신벌레의 번식 정보 $a$, $b$, $d$에 대하여, 새로 태어난 짚신벌레 한 마리를 수조 안에 넣은 이후 $N$일째 되는 날 살아있는 짚신벌레 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

첫째 줄에 $a, b, d, N$을 나타내는 네 정수가 공백 하나를 사이에 두고 차례로 주어진다. 단, $0 < a < b < d \le 10000$이고, $1 \le N \le 1000000$이다.

첫째 줄에, 수조에 짚신벌레 한 마리를 넣은 지 $N$일째 되는 날 수조에 살아 있는 짚신벌레의 수를 1000으로 나눈 나머지를 출력한다.