A2. Heidi Learns Hashing (Medium)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAfter 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.InputThe 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.OutputOutput a single integer: the number of suitable values of k.ExampleInput
4
1010
Output
3
NoteIn 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.
4
1010

3 
['brute force', 'number theory', '*2100']