题目描述

有一个字符串只有０和１组成，对于某个子串，如果将０和１互换并且倒过来与原子串相同，则认为该子串是＂反对称＂的。 给出一个长度为Ｎ的字符串，那么有多少个子串是＂反对称＂的？

输入格式

第一行一个正整数Ｎ（０＜＝Ｎ＜＝10000）． 第二行包括一个长度为Ｎ的01串．

输出格式

输出＂反对称＂子串的个数．

样例

输入

8

输出

11001011

7

来源

CodesOnline