A2. Хайди изучает хеширование (средняя)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того, как Хайди изучила полиномиальное хеширование, она решила изучить хэширование через битовый сдвиг и xor. В частности, она наткнулась на следующую задачу:

Дана битовая строка $$$y \in \{0,1\}^n$$$. Нужно посчитать количество $$$k$$$ ($$$0 \leq k < n$$$), таких что существует $$$x \in \{0,1\}^n$$$, такой что $$$y = x \oplus \mbox{shift}^k(x).$$$

Где $$$\oplus$$$ обозначает побитового xor, а $$$\mbox{shift}^k$$$ обозначает операцию циклического сдвига битовой строки направо $$$k$$$ раз. Например, $$$001 \oplus 111 = 110$$$, а $$$\mbox{shift}^3(00010010111000) = 00000010010111$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длину битовой строки $$$y$$$.

Вторая строка содержит битовую строку $$$y$$$.

Выходные данные

Выведите одно целое число: количество подходящих $$$k$$$.

Пример
Входные данные
4
1010
Выходные данные
3
Примечание

В первом примере:

  • $$$1100\oplus \mbox{shift}^1(1100) = 1010$$$
  • $$$1000\oplus \mbox{shift}^2(1000) = 1010$$$
  • $$$0110\oplus \mbox{shift}^3(0110) = 1010$$$

Не существует $$$x$$$, такого что $$$x \oplus x = 1010$$$, а значит ответ равен $$$3$$$.