ПРИМЕЧАНИЕ: это - более сложный вариант задачи 114.

В ряд длиной n единиц помещены красные блоки длиной по крайней мере m единиц так, что любые два красных блока (длины которых могут и отличаться) разделены между собой хотя бы одним черным квадратом со стороной единица.

Пусть функция числа заполнений F(m, n) указывает количество способов, которыми можно заполнить ряд.

К примеру, F(3, 29) = 673135 и F(3, 30) = 1089155.

Это значит, что при заданном значении m = 3, значение n = 30 является наименьшим, при котором значение функции числа заполнений превышает один миллион.

Аналогичным образом, при заданном значении m = 10, можно убедиться в том, что F(10, 56) = 880711 и F(10, 57) = 1148904, так что n = 57 является наименьшим значением, при котором значение функции числа заполнений превышает один миллион.

Дано, что m = 50. Найдите наименьшее значение n, при котором значение функции числа заполнений превысит один миллион.