115 : ブロックの組み合わせ方の数え上げ その2

注意: これは問題114をより難しくした問題である.

長さ$n$ユニットからなる 1 列上に, 最低$m$ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数$F(m, n)$は 1 列に敷き詰める方法が何通りかを表すとする.

例えば,$F(3, 29) = 673135$であり,$F(3, 30) = 1089155$である.

$m = 3$の時,$n = 30$がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

同様に,$m = 10$では$F(10, 56) = 880711, F(10, 57) = 1148904$であることがわかり, つまり$n = 57$がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

$m = 50$のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の$n$の値を求めよ.