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

A row measuring units in length has red blocks with a minimum length of units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this for and .

How many ways can a row measuring units in length be filled? As the answer can be extremely large, print it modulo .

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length (and ) you could use red (), black (), and red ().