Let \(L\) be the length of \(s\). For \(i = 0, \ldots, L\), let \(A_i\) and \(B_i\) be, respectively, the number (\(\mathrm{mod}~n\)) of \(1\)s, and the number of \(0\)s (\(\mathrm{mod}~m\)) among the first \(i\) characters of \(s\). The condition then amounts to:

• \(A_L = B_L = 0\),
• pairs \((A_i, B_i)\) do not repeat, aside from \((A_0, B_0) = (A_L, B_L) = (0, 0)\).

A different interpretation is as follows: construct a grid graph with \(n \times m\) vertices, where vertex \((x, y)\) (\(0 \leq x < N\), \(0 \leq y < M\)) has edges to \(((x + 1) \bmod n, y)\) and \((x, (y + 1) \bmod m)\). In this graph we need to count simple cycles starting at the vertex \((0, 0)\). For now, let’s count all the simple cycles, regardless of \((0, 0)\).

Suppose we have fixed a set of rows \(R\) and a set of columns \(C\) where the cycle wraps around the grid. Any such cycle corresponds to a vertex-disjoint path collection connecting top/leftmost cells with bottom/rightmost cells of \(R\) and \(C\). By LGV lemma the number of such path collections is \((-1)^{|R| \times |C|} \times\) the determinant of the \((|R| + |C|) \times (|R| + |C|)\) matrix, which elements are numbers of paths from each starting cell to each finishing cell. However, note that paths merge into a single cycle if and only if \(|R|\) and \(|C|\) are coprime.

To compute path counts for all \(|R|, |C|\) modify the graph as follows (\(x, y\) are variable weights, unmarked edges have weight \(1\), \(+\) and \(-\) are respectively source and sink vertices):

Applying LGV lemma to this graph, we obtain the total product weight over all path collections as a polynomial \(\sum_{r, c} A_{r, c} x^r y^c\). The answer is then equal to \(\sum_{r, c\text{ coprime}} (-1)^{rc} A_{rc}\).

If we want to only include paths that, say, wrap around the first row, we erase the source-sink edge in the first row of the grid. A cycle passes through \((0, 0)\) if it wraps around the first row, or the first column.

Computing determinant symbolically is hard, but we can compute it at \(O(NM)\) points \((x, y)\) and interpolate. Total complexity is \(O(N^2M^2(N + M))\) (if one utilizes block-triangular structure of the path-counting matrix).