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-----

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-----

Output a single integer: the number of suitable values of $k$.


-----Example-----
Input
4
1010

Output
3



-----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$.

Difficulty: interview

Starter code:

Solutions:
from collections import deque
import math

num = int(input())
x = tuple(map(int, list(input())))

#if x == "0"*num: print(num); return

integer = 0

dic = dict()

for i in range(1,num+1):
    a = math.gcd(i,num)
    if a in dic:
        integer += dic[a]
    else:
        lijst = [0]*a
        
        for j in range(num):
            b = j%a
            lijst[b] += x[j]

        for k in range(a):
            if lijst[k]%2 != 0:
                dic[a] = 0
                break
        else:
            integer += 1
            dic[a] = 1
print(integer)

import math

num = int(input())
x = tuple(map(int, list(input())))

integer = 0

dic = dict()

for i in range(1,num+1):
    a = math.gcd(i,num)
    if a in dic:
        integer += dic[a]
    else:
        lijst = [0]*a
        
        for j in range(num):
            b = j%a
            lijst[b] += x[j]

        for k in range(a):
            if lijst[k]%2 != 0:
                dic[a] = 0
                break
        else:
            integer += 1
            dic[a] = 1
print(integer)

import sys
import math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()

a = [1] * n
for c in s:
	if c != '0':
		a[0] = 0

for k in range(1, n):
	if n % k == 0:
		t = [0] * k
		for i, c in enumerate(s):
			if c != '0':
				t[i % k] += 1
		if sum([_ % 2 for _ in t]) != 0:
			a[k] = 0
	else:
		a[k] = a[math.gcd(n, k)]

sys.stdout.write('{0}\n'.format(sum(a)))


from math import gcd

def canHash(n, ln):
    if n == '0'*ln:
        return ln
    ans = 0
    yes = []
    for i in range(1, ln):
        if ln%i == 0:
            token = 1
            for k in range(i):
                a = sum([int(b) for b in n[k::i]])
                if a%2 != 0:
                    token = 0
            if token == 1:
                yes.append(i)
                ans += 1
        else:
            if gcd(ln, i) in yes:
                ans += 1
    return ans


def __starting_point():
    ln = int(input())
    print(canHash(input(), ln))
__starting_point()