- All Contests
- ProjectEuler+
- Project Euler #191: Prize Strings

# Project Euler #191: Prize Strings

# Project Euler #191: Prize Strings

_{This problem is a programming version of Problem 191 from projecteuler.net}

A particular school offers cash rewards to children based on their score history.

During an - period, a string (scores) is formed, for each child, in the following way:

where is the score of the child at the day.

If they get for consecutive days on more than occasion(s) then they forfeit their prize.

For a given , , and , let's call strings for which the child gets his prize , and denote the number of prize strings for these parameters.

For example, with (- period), , and , it can be verified that and here are the different prize strings that can be formed:

.

You are given , , and , what is .

**Input Format**

The only line of each test case contains exactly four integers separated by single spaces: , , and

**Constraints**

**Output Format**

Print the answer modulo

**Sample Input**

```
4 1 3 3
```

**Sample Output**

```
73
```

**Explanation**

, , and . Hence the sum is .