Klötzchenkombinationen zählen II

Problem 115

HINWEIS: Das ist eine schwierigere Variante von Problem 114.

Eine Zeile der Länge n Einheiten ist so mit roten Kötzchen einer Mindestlänge m belegt, dass mindestens ein schwarzes Feld sie trennt. Dabei ist die Länge der roten Klötzchen unabhängig voneinander wählbar.

Wir definieren mit F(m, n) eine Füllzählfunktion, die die unterschiedlichen Varianten, eine Zeile zu belegen, zählt.

Beispielsweise gilt F(3, 29) = 673135 und F(3, 30) = 1089155.

Somit ist für m = 3 der Wert n = 30 der kleinste Wert, mit dem die Füllzählfunktion erstmais eine Million überschreitet.

Ähnlich kann für m = 10 gezeigt werden, dass F(10, 56) = 880711 und F(10, 57) = 1148904 gilt, sodass mit n = 57 erstmals die Füllzählfunktion mehr als eine Million Belegungen zählt.

Finden Sie für m = 50 den kleinsten Wert n, für den die Füllzählfunktion größer als eine Million ist.