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 .
The only line of each test case contains exactly four integers separated by single spaces: , , and
Print the answer modulo
4 1 3 3
, , and . Hence the sum is .