题目背景

涙目 変わらずの雨模様
泪眼不变的烟雨迷蒙
その夢の淵ギリギリで
在那梦的深渊倾盆而下
—— ヒトリエ《Namid[A]me》

最终，只剩我一人了。

题目描述

给定小写英文字母和 ? 组成的字符串 $s$。

“泪雨”定义为这样的串：这是一个回文串，并且 ? 的个数大于等于小写英文字符的个数。

请对于是“泪雨”的 $s$ 的所有子串，求出它们问号位置的和之和。（位置下标从 $1$ 开始）

形式化题意：定义：

$$f(l,r)= \sum_{i=l}^{r} [s_i=\texttt{?}]\cdot i \\ g(l,r)=\big[\sum_{i=l}^r{[s_i=\texttt{?}] \geq} \frac{r-l+1}{2}\big]\big[ s[l,r]\text{ is a palindrome} \big] $$

请你求出 $\sum_{l=1}^{n} \sum_{r=l}^{n} g(l,r)\cdot f(l,r)$，其中 $n=\lvert s\rvert$。

输入格式

第一行一个正整数 $n$，表示 $s$ 的长度 $n$。

第二行输入仅由小写英文字母和问号组成的字符串 $s$。

输出格式

一行一个正整数，表示答案。

4
a??a

15

10
?a?aa?a?a?

115

提示

样例解释： 样例 $1$ 中，$[2,2],[3,3],[1,4],[2,3]$ 都是符合要求的回文串，并且所求的问号位置之和为 $2+3+(2+3)+(2+3)=15$。

以下是数据范围。

Subtask	$n$	特殊性质	分值	子任务依赖
$1$	$\leq 500$	无	$10$	-
$2$	$\leq 7000$		$15$	$1$
$3$	$\leq 2\times 10^6$	$s$ 中仅有 ?	$5$	-
$4$		字符串随机生成	$10$	$1$
$5$		$s$ 中有且仅有两种字符		-
$6$	$\leq 3\times 10^5$	无	$15$	$1,2$
$7$	$\leq2\times 10^6$			$1\sim 6$
$8$	$\leq 5\times10^6$	$\text{timelimit}=1.5s$	$20$	$1\sim 7$

对于 $100\%$ 的数据满足 $1\leq n\leq 5\times 10^6$，且 $s$ 仅包含小写英文字母和 ?。

除了 $\text{subtask 8}$ 之外，时限皆为 $1s$。

时间限制已开到了 std 的 2 倍以上，空间限制开到了 std 的 1.25 倍以上，但仍需 注意程序的运行时空常数。