Paramecia

Interview

Time limit1sMemory limit128 MB

Summary

Simulate a population where each individual matures, reproduces daily within an age window, dies at a fixed age, and count survivors on day N modulo 1000.

Level: Medium5 of 10
Topics: Dynamic programming, Simulation, Math
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples2

Example 1
Input
```
2 4 6 6
```
Expected output
```
7
```
Example 2
Input
```
3 5 7 20000
```
Expected output
```
609
```