Description:
After learning about polynomial hashing, Heidi decided to learn about shift-xor hashing. In particular, she came across this interesting problem.
Given a bitstring $$$y \in \{0,1\}^n$$$ find out the number of different $$$k$$$ ($$$0 \leq k < n$$$) such that there exists $$$x \in \{0,1\}^n$$$ for which $$$y = x \oplus \mbox{shift}^k(x).$$$
In the above, $$$\oplus$$$ is the xor operation and $$$\mbox{shift}^k$$$ is the operation of shifting a bitstring cyclically to the right $$$k$$$ times. For example, $$$001 \oplus 111 = 110$$$ and $$$\mbox{shift}^3(00010010111000) = 00000010010111$$$.
Input Format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the bitstring $$$y$$$.
The second line contains the bitstring $$$y$$$.
Output Format:
Output a single integer: the number of suitable values of $$$k$$$.
Note:
In the first example:
- $$$1100\oplus \mbox{shift}^1(1100) = 1010$$$
- $$$1000\oplus \mbox{shift}^2(1000) = 1010$$$
- $$$0110\oplus \mbox{shift}^3(0110) = 1010$$$
There is no $$$x$$$ such that $$$x \oplus x = 1010$$$, hence the answer is $$$3$$$.