Задача . F. Нули и единицы

Пусть \(S\) — это строка Туэ-Морса. Другими словами, \(S\) — это пронумерованная с \(0\) бинарная строка бесконечной длины, построенная следующим образом:

• Изначально \(S\) равна «0».
• Затем мы повторяем следующую операцию бесконечно много раз: конкатенируем \(S\) с ее копией, в которой все биты заменены на противоположные по значению.

  Например, ниже показаны первые четыре операции:

  Номер операции	\(S\) до операции	\(S\) до операции с заменой бит	Сконкатенированная \(S\)
  1	0	1	01
  2	01	10	0110
  3	0110	1001	01101001
  4	01101001	10010110	0110100110010110
  \(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)

Вам даны два положительных числа \(n\) и \(m\). Найдите количество позиций, в которых отличаются строки \(S_0 S_1 \ldots S_{m-1}\) и \(S_n S_{n + 1} \ldots S_{n + m - 1}\).