Последовательность Туе-Морса-Радецки-Матеуша (Туорса-Радевуша, для краткости) это бесконечная последовательность, получающаяся из конечной последовательности $$$\mathrm{gen}$$$ длины $$$d$$$ и целого числа $$$m$$$, следующим образом:

• В начале мы определяем $$$M_0=(0)$$$.
• На $$$k$$$-м шаге, $$$k \geq 1$$$, мы определяем $$$M_k$$$ как конкатенацию $$$d$$$ копий $$$M_{k-1}$$$. Однако, каждая из них немного изменяется — в $$$i$$$-й из них ($$$1 \leq i \leq d$$$) каждый элемент $$$x$$$ заменяется на $$$(x+\mathrm{gen}_i) \pmod{m}$$$.

Например, если $$$\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})$$$ и $$$m = 4$$$:

• $$$M_0 = (0)$$$,
• $$$M_1 = (0, \color{blue}{1}, \color{green}{2})$$$,
• $$$M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0})$$$,
• $$$M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2})$$$, и так далее.

Как можно заметить, при условии, что первый элемент $$$\mathrm{gen}$$$ равен $$$0$$$, каждый последующий шаг порождает последовательность, префиксом которой является последовательность с предыдущего шага. Тогда мы можем определить бесконечную последовательность Туорса-Радевуша $$$M_\infty$$$ как последовательность, получаемую бесконечным применением шага выше. Например, для параметров выше, $$$M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)$$$.

Матеуш выбрал последовательность $$$\mathrm{gen}$$$ и целое число $$$m$$$, и с помощью них получил последовательность Туорса-Радевуша $$$M_\infty$$$. Затем он выбрал два целых числа $$$l$$$ и $$$r$$$ и записал подпоследовательность этой последовательности: $$$A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r)$$$.

Обратите внимание, что мы используем нумерацию с $$$1$$$ для $$$M_\infty$$$ и $$$A$$$.

У Матеуша есть его любимая последовательность $$$B$$$ длины $$$n$$$ и хочет узнать, насколько она большая относительно $$$A$$$. Он говорит, что последовательность $$$B$$$ мажорирует последовательность $$$X$$$ длины $$$n$$$ (обозначим как $$$B \geq X$$$), если для всех $$$i \in \{1, 2, \dots, n\}$$$ выполняется $$$B_i \geq X_i$$$.

Теперь он спрашивает себя, сколько существует целых чисел $$$x$$$ в отрезке $$$[1, |A| - n + 1]$$$ таких, что $$$B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1})$$$. Так как обе последовательности очень большие, то ответить на вопрос, используя только бумагу и ручку, оказалось затруднительно. Не могли бы вы ему помочь?