题目描述

对于一个仅包含 0 和 1 的字符串，先将其中原来的 0 变成 1，原来的 1 变成 0，再将得到的字符串整个逆序，如果此时得到的串和原串相同，则称原字符串为“可回归串”。

现在给出一个长度为 N 的仅包含 0 和 1 的字符串，问：它有多少个子串是可回归串。

注意：如果两个子串的内容是相同的，但出现的位置不同，则被认为是不同的子串。

样例输入

6
110010

110010

共 25 个测试点，全部满足：N <= 10^7

其中 3 个测试点：N <= 10^3

另有 4 个测试点：N <= 10^4

另有 10 个测试点：N <= 10^6

另有 8 个测试点：N <= 10^7