题目描述

你是某知名 CP 网站的比赛审核员，经常收到一些 standard 的投稿。

你已经使用了太多次「quite standard」和「somewhat standard」作为回复了，因此这次你决定换一些。

首先你写下了你对这道题的评价 $s$，这里 $s$ 是一个仅包含英文小写字母的字符串。为了让投稿者知道自己的题目有多 standard，你又将这个字符串 $s$ 粘贴了 $k-1$ 次。最终，你的评价形成了一个字符串 $t = s^k$。

投稿者定义一个回复的 怪异度 是这个字符串里的回文子串数量。请你求出你写下的回复 $t$ 的怪异度。由于这个值可能很大，你只需要输出它对 $998244353$ 取模的结果。

形式化的，给定字符串 $s$ 和整数 $k$，求 $s^k$（字符串 $s$ 拼接 $k$ 次）有多少回文子串（位置不同即算作不同），模 $998244353$。

输入格式

本题含有多组输入数据。

第一行一个整数 $t(1 \le t \le 10^4)$ 表示数据组数。

对于每组数据，第一行两个整数 $n,k(1 \le n \le 3 \cdot 10^6,1 \le k \le 10^9)$ 表示字符串长度和拼接次数。

第二行一个长度为 $n$ 的只包含小写字母的字符串 $s$。

保证单组数据内 $\sum n \le 3 \cdot 10^6$。

输出格式

对于每组数据，输出一个整数表示答案对 $998244353$ 取模的结果。

3
4 2
abab
1 1
a
30 1
abaababaababaababaababaababaab

20
1
128

提示

样例解释

对于第一组数据，$t = s^2 = \texttt{abababab}$，共有 $20$ 个回文子串。

对于第三组数据，输入的字符串是 $(\texttt{abaab})^6$。

数据范围

子任务 $1$ 为样例，不计分。

子任务	分数	$n \le$	$k \le$
$2$	$5$	$2$	$10^9$
$3$	$30$	$3 \cdot 10^6$
$4$		$2000$	$10^9$
$5$	$35$	$3 \cdot 10^6$

• 子任务 $3$ 保证 $\sum k \le 3 \cdot 10^6$。
• 子任务 $4$ 保证 $\sum n^2 \le 2.5 \cdot 10^7$。