It is impossible to reach Square \(N\) if and only if there are \(M\) or more consecutive squares that send him to Square \(0\). It is easy to check that, so let us assume that it is possible to reach Square \(N\).

Let \(f(i)\) be the expected value of the number of moves, starting from Square \(i\).

First, consider the case where there are no such squares that send him to Square \(0\). In such case, an equation \(f(i)=\dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1\) holds. So, we can find \(f(i)\) in the increasing order of \(f(i)\) while calculating the cumulative sums in order to find \(f(0)\) in a total of \(O(N)\) time.

Now let us consider that there are such squares that send him to Square \(0\). In such case,

\(f(i)= \begin{cases} f(0) & \text{If Square i sends him to Square 0} \\ \dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1 & \text{otherwise} \end{cases} \)

Unlike before, the relations are cyclic, so it seems that they cannot be calculated.

Solution 1　Use linear expression

Let \(X\) be a variable. Define a function \(g\) that yields a linear expression:

\(f(i)= \begin{cases} X & \text{If Square i sends him to Square 0} \\ \dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1 & \text{otherwise} \end{cases} \)

Now that the relations are no longer cyclic, one can find \(g(i)\) with in a similar way to where there are no squares that send him to Square \(0\).

We obtain \(g(0)=A*X+B\), but when \(f(0)\) is assigned to \(X\), \(g\) will be equal to \(X\) by the definition of \(g\), so we obtain \(f(0)=g(0)=A*f(0)+B\). By solving this linear equation, we can find \(f(0)\).

The total time complexity is \(O(N)\).

Solution 2　Binary search

Let \(P\) be a constant. Define a function \(h\) with:

\(h(i)= \begin{cases} P & \text{If Square i sends him to Square 0} \\ \dfrac{1}{M}(f(i+1)+\ldots+f(i+M))+1 & \text{otherwise} \end{cases} \)

Now that the relations are no longer cyclic, one can find \(g(i)\) with in a similar way to where there are no squares that send him to Square \(0\).

Here, the following relationships are true:

• If \(P\geq f(0)\), then \(h(0)\leq P\).
• If \(P\leq f(0)\), then \(h(0)\geq P\).

(One can prove them by assigning \(P\) to \(X\) in \(g\) defined in Solution 1. Note that \(A \leq 1\))

Therefore, one can find \(f(0)\) with binary search. Under the constraints given this time, \(f(0)\) can be up to \(N4^K/2≒5\times 10^{10}\), so be careful of the upper bound of the search.

Since we perform an \(O(N)\) DP inside the binary search, so the time complexity is \(O(NT)\), where \(T\) is the number of iterations.

In this problem, the relative error is smaller than the absolute error, so one can set the medium value to \(\sqrt{low \times high}\) instead of \((low + high)/2\) in order to decrease the number of iterations.

In general, if the upper bound of binary search is unknown, one can check the appropriate upper bound exponentially like \(1\to 2 \to 4\to 8\to\ldots\).