Complementary Gene Pairs

Blue discovered an unusual creature whose genetic information is represented by a binary string \(s = s_0s_1\cdots s_{n-1}\) of length \(n\). Any contiguous substring \(s_{l,r} = s_l s_{l+1} \cdots s_r\) (with \(0 \leq l \leq r < n\)) can be considered a gene.

We say that two positions in the genetic information are complementary if the characters at these two positions are different (i.e. one is 0 and the other is 1).

Blue wonders: How many pairs of non-overlapping genes of the same length exist such that they are exactly complementary? In other words, count the number of pairs \( [(a,b), (c,d)] \) satisfying:

• \(0 \leq a \leq b < c \leq d < n\), and
• \(b - a = d - c\) (i.e. both genes have the same length), and
• For every \(i \; (0 \leq i \leq b-a)\), we have \(s_{a+i}\) and \(s_{c+i}\) is a complementary pair, i.e. \(s_{a+i} \neq s_{c+i}\).

Find the total number of such pairs.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) representing the length of the genetic information.
2. The second line contains a binary string \(s\) of length \(n\), consisting only of characters '0' and '1'.

outputFormat

Output a single integer, the total number of pairs of disjoint genes (substrings) of equal length that are complementary in every position.

sample

4
1010

3