참고 : 이 문제는 114번의 고난이도 버전입니다.

길이가 n 인 칸에 빨간 블록들을 놓습니다. 빨간 블록의 길이는 적어도 m칸 이상이고, 블록과 블록 사이는 최소 한 칸 이상 떨어져야 합니다 (블록들의 크기는 달라도 상관없습니다).

이 때 빨간 블록을 놓을 수 있는 경우의 수를 F(m, n) 라는 함수로 나타내기로 합니다.

예를 들자면 F(3, 29) = 673135 이고 F(3, 30) = 1089155 입니다.

즉, m = 3 일 경우, F 값이 1백만을 넘게 되는 최초의 n 은 30 임을 알 수 있습니다.

같은 식으로 하여 m = 10 에서는 F(10, 56) = 880711 이고 F(10, 57) = 1148904 이므로,
F 값이 1백만을 넘는 최초의 n 은 57이 됩니다.

그러면 m = 50 일 때, F 값이 1백만을 넘는 최초의 n 은 얼마입니까?