Học Băm Dịch-XOR (Trung bình)

Cho một xâu nhị phân $y\in \{0,1{\}}^n$ có độ dài $n$. Hãy đếm số giá trị $k$ khác nhau với $0\le k<n$ sao cho tồn tại một xâu nhị phân $x\in \{0,1{\}}^n$ thỏa mãn:

$$y=x\oplus {\text{shift}}^k(x)$$

Trong đó $\oplus$ là phép XOR theo từng bit, còn ${\text{shift}}^k$ là phép dịch vòng (cyclic shift) xâu sang phải $k$ lần.

Ví dụ: $001\oplus 111=110$, và ${\text{shift}}^3(00010010111000)=00000010010111$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, độ dài của xâu $y$.
• Dòng thứ hai chứa xâu nhị phân $y$.

Dữ liệu ra

• In ra một số nguyên: số giá trị $k$ hợp lệ.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $y$ chỉ gồm các ký tự 0 và 1, độ dài đúng bằng $n$.

Ví dụ