После того, как Хайди изучила полиномиальное хеширование, она решила изучить хэширование через битовый сдвиг и 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\).
Выходные данные
Выведите одно целое число: количество подходящих \(k\).
Примечание
В первом примере:
- \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1010
|
3
|