回文字符串的概念大家都知道，如果一个字符串反过来和正过来相同，则该字符串为回文串，比如：12321，123321 都是回文字符串，但字符串 1100 不是回文字符串。

现给出反回文串的定义：如果一个仅包含字符 0 和字符 1 的字符串，将该字符串中的 0 修改为 1、 1 修改为 0 之后，再将字符串颠倒过来和原字符串相同，则称之为反回文串；如，字符串：0011、0101 都是反回文串，但字符串 0110 不是反回文串。

给定一个长度为 N 的仅包含字符 0 和字符 1 的字符串，请编程计算出，该字符串包含了多少个反回文子串。

第 1 行读入一个整数 N，代表读入字符串的长度。 ( 1 \le N \le 5 \times 10^5)。

第 2 行读入 N 个字符，每个字符不是 0，就是 1。

输出一个整数，代表字符串中的反回文子串的数量。

样例 1 解释

字符串中包含的反回文子串有：01（出现 2 次），10 （出现 2 次），0101 （出现 1 次），1100 （出现 1 次），001011 （出现 1 次）。

共计出现了 7 个反回文子串。

POJ

哈希