变长记录里的相邻对

题目描述

第 i 轮把当前字符串改成“旧串、字符 c_i、旧串的倒序副本”。求 n 轮后，有多少对相邻位置上的字符相同。每一对按位置计算，一段 aaa 含两对相邻相同字符。

输入格式

第一行 n；第二行初串 w；n>0 时第三行给长度 n 的插入字符串，n=0 时没有第三行。

输出格式

输出相邻相同对数。

样例 1

输入

2
ab
bb

输出

4

说明

第一轮为 abbba，有两对；第二轮两个连接处不同，仅复制成四对。

样例 2

输入

0
aaa

输出

2

说明

三个相同字符只有两对相邻位置。

数据范围

• 0≤n≤50；1≤|w|≤5；均为小写字母；答案使用 long long。