在学习了多项式哈希之后,Heidi 决定学习移位异或哈希。特别是,她遇到了这个有趣的问题。
给定一个位串 $$$y \in \{0,1\}^n$$$ 找出不同 $$$k$$$ ($$$0 \leq k < n$$$) 的数量,使得存在 $$$x \in \{0,1\}^n$$$ ,其中 $$$y = x \oplus \mbox{shift}^k(x)。$$$
上面的 $$$\oplus$$$ 是异或运算,$$$\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$$$ 的合适值的数量。
示例
输入 #1
4 1010
输出 #1
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$$$。