We construct a directed graph with ~N~ vertices, labeled by numbers ~1~ to ~N~. All edges will be of the form ~permutation[k] \to k~ for each ~k~ smaller than or equal to ~N~ where ~permutation[]~ is the shuffle sequence given in the input. It is clear that each vertex has exactly one incoming and one outgoing edge, because for each ~x~ and ~y~, ~permutation[x] \ne permutation[y]~ is ~x \ne y~. Such a graph contains one or more components, where each component is a cycle of length ~p~. Note that this graph uniquely represents the output sequence of Mirko's machine.

We now compute cycle lengths for each component. We construct an array ~cycle[X]~ that stores the length of the cycle containing vertex ~X~. This can be constructed in ~\mathcal O(N)~ time. We can now determine for any columns ~C~ to ~D~ the number of rows between two repetitions of the original ordering as ~P = \operatorname{lcm}(cycle[C], cycle[C+1], \dots, cycle[D])~ where ~\operatorname{lcm}~ is the least common multiple function. We now know that the rows we are interested in are given as ~1 + q \times P~ where ~q~ is a nonnegative integer. The solution to the original problem is now the number of nonnegative integers ~q~ that satisfy:

$$\displaystyle A \le 1 + q \times P \le B$$

This can be easily solved.