Let ~V[i]~ be ~\text{true}~ if ~i~ is a valid number at which the given sequence of ~M~ words could've started at (in other words, if ~i~ could've been the ~M~-th last number in the game), and ~\text{false}~ otherwise. For a given ~i~, we can determine the value of ~V[i]~ in ~\mathcal O(M)~ time with simulation by testing if, for each ~j~ from ~1~ to ~M~, the ~j~-th words are the correct words for number ~i+j-1~.

The simulation is very similar to naively searching through a string, where all ~N~ rounds of the game form a "haystack" to be searched through and the ~M~ words is the "needle" of which we must count occurrences.

To test all ~N-M+1~ possible starting indices, the overall running time is ~\mathcal O((N-M+1) \times M) = \mathcal O(NM)~ since ~N~ is significantly larger than ~M~. However, this will not pass since ~N~ is as big as ~10^9~. Even using faster string searching algorithms such as the KMP or Aho-Corasick algorithms will not pass, as their time complexities all depend on ~N~.

To get full marks, we will have to eliminate the bottleneck of generating the words of all ~N~ rounds of the game. The trick is to notice that in a perfect game of FizzBuzzOok, the sequence of words repeats after every ~15~ terms. This also means that ~V~ repeats every ~15~ terms – that is, if the sequence could have started at number ~i~, it could have also started at number ~i+15j~ (for any non-negative integer ~j~). Therefore, we only need to compute ~V[1 \dots 15]~ using the above approach (in a total of ~\mathcal O(M)~ time), and can then observe that ~V[16] = V[1]~, ~V[17] = V[2]~, and so on.

To compute the answer, then, we should consider each value of ~i~ between ~1~ and ~15~ for which ~V[i] = \text{true}~, and count the number of non-negative integers ~j~ such that ~i+15j \le N-M+1~ (which is the largest number that could've been the first word in the given sequence). Using some algebra to rearrange this inequality, we get ~15j \le N-M-i+1~, which ultimately implies that ~j \le \frac{N-M-i+1}{15}~.

Assuming the left-hand side formula is non-negative, then the number of possible non-negative integers ~j~ is equal to the expression rounded down, plus ~1~ to account for ~0~ being a valid value of ~j~. If it happens that the left-hand side expression is negative, then we should report ~0~ as the answer. These two cases can be merged into the expressions ~\lceil \frac{N-M-i+2}{15} \rceil = \lfloor \frac{N-M-i+16}{15} \rfloor~. A solution which implements this idea has a running time of ~\mathcal O(M)~.