k-palindrome

题号：NC217923
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一个长度为 ${n}$ 的字符串 ${S}$ 被称为 ${k-palindrome}$ 当前仅当以下条件满足：
1.对于 $i=\{1,2,...,n\},S_i=S_{n-i+1}$ .
2.若 ${k>1}$ 则 $S_1S_2...S_{\lfloor\frac{n}{2}\rfloor}$ 和 $S_{n-\lfloor\frac{n}{2}\rfloor+1}...S_{n-1}S_n$ 都是 ${(k-1)-palindrome}$ .
令 ${G}$ 为 ${S}$ 的本质不同的非空子串构成的集合。

对于 ${k=\{1,2,...,m\}}$ ，计算 ${G}$ 中有多少个 ${k-palindrome}$ 。

令当 ${k=i}$ 时的答案为 ${ans_i}$ 。

输出 ${\sum\limits_{i=1}^m}ans_i*2^i\bmod 998244353$

输入描述:

输入包含组测试用例，第一行一个整数。
每组案例第一行两个整数。
每组案例第二行一场长度为的字符串。

输出描述:

输出行第行一个整数表示第组测试用例的答案。

示例1

输入

复制

1
3 2
aba

输出

复制

说明

，答案为

备注:


仅包含小写英文字符。