Paramecia

A biologist is observing the reproduction of a newly discovered paramecium species. The species reproduces asexually, and on day 0 one newborn individual is placed in a tank.

Each individual behaves according to its age, measured as the number of whole days since it was born.

• When its age becomes a, it becomes mature.
• On every day with age at least a and less than b, it produces exactly one newborn. It also produces one on the day it first becomes mature.
• Starting from age b, it no longer produces newborns. Therefore, one individual produces exactly b - a newborns during its lifetime.
• When its age becomes d, it dies and disappears from the tank.

After the growth, births, and deaths for each day have been reflected, the individuals still in the tank are counted. Given a, b, d, and N, compute the number of individuals alive on day N.

The first line contains four integers a, b, d, and N, separated by spaces.

0 < a < b < d <= 10,000, 1 <= N <= 1,000,000

Print the number of individuals alive in the tank on day N, modulo 1000.