Palindromic Value
题号：NC313666
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯有一个长度为 n 的字符串 s，仅由小写字母组成。
\hspace{15pt}小苯可以将 s 分割为若干个非空子串^\texttt{[1]}，要求每个子串都是回文串^\texttt{[2]}。
\hspace{15pt}定义一种分割方案的价值为：所有子串长度的平方和。更具体地，将 s 表示为 s = t_1 t_2 \cdots t_k 的一种写法，其中 t_i 为 s 的非空连续子串，且每个 t_i 都是回文串。分割方案的价值为 \sum_{i=1}^k (|t_i|)^2，其中 |t_i| 表示 t_i 的长度。

\hspace{15pt}记所有不同分割方案（分割点集合不同视为不同方案）的价值之和为答案。
\hspace{15pt}你的任务就是求出这个答案。由于答案可能很大，请将答案对 998\,244\,353 取模后输出。

【名词解释】
\hspace{15pt}子串^\texttt{[1]}：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
\hspace{15pt}回文串^\texttt{[2]}：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。

输入描述:

\hspace{15pt}每个测试文件包含多组测试数据。第一行输入一个整数 T\left(1 \leqq T \leqq 100 \right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行一个整数 n\left(1 \leqq n \leqq 2 \times 10^3 \right)。
\hspace{15pt}第二行一个长度为 n，仅由小写字母组成的字符串 s。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^3。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个整数，表示所有回文分割方案的价值总和对 998\,244\,353 取模的结果。
示例1

输入

复制 
2
3
aba
2
ab

输出

复制 
12
2

说明

\hspace{15pt}对于第一组测试数据，s = \texttt{aba}，有两种可行分割方案：
\hspace{23pt}\bullet\,拆分为 \texttt{a}、\texttt{b}、\texttt{a}，价值 1^2 + 1^2 + 1^2 = 3；
\hspace{23pt}\bullet\,保持原状，价值 3^2 = 9。

\hspace{15pt}对于第二组测试数据，s = \texttt{ab}，唯一可行方案为拆分为：
\hspace{23pt}\bullet\,\texttt{a}、\texttt{b}，价值 1^2 + 1^2 = 2。
示例2

输入

复制 
1
4
aaaa

输出

复制 
66

说明

\hspace{15pt}对于第一组测试数据，s = \texttt{aaaa}，任意子串均为回文串，所有分割方案对应将 4 分拆为有序正整数和：
\hspace{23pt}\bullet\,1+1+1+1：价值 1+1+1+1 = 4；
\hspace{23pt}\bullet\,1+1+2：价值 1+1+4 = 6；
\hspace{23pt}\bullet\,1+2+1：价值 1+4+1 = 6；
\hspace{23pt}\bullet\,2+1+1：价值 4+1+1 = 6；
\hspace{23pt}\bullet\,1+3：价值 1+9 = 10；
\hspace{23pt}\bullet\,3+1：价值 9+1 = 10；
\hspace{23pt}\bullet\,2+2：价值 4+4 = 8；
\hspace{23pt}\bullet\,4：价值 16。
\hspace{15pt}总和为 4+6+6+6+10+10+8+16 = 66。

备注: