Description

As a contest reviewer for a well-known CP platform, you often receive standard problem submissions.

Having overused replies like "quite standard" and "somewhat standard", you decide to try something new.

First, you write your review $s$ (a lowercase English string). To emphasize how standard the problem is, you concatenate $s$ $k-1$ times to form the final reply $t = s^k$.

The submitter defines the weirdness of a reply as the number of palindromic substrings in it. Your task is to compute the weirdness of $t$ modulo $998244353$.

Formally, given string $s$ and integer $k$, find the number of distinct palindromic substrings (counted by position) in $s^k$ (the concatenation of $k$ copies of $s$), modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $t$ $(1 \le t \le 10^4)$ indicating the number of test cases.

For each test case:

• The first line contains two integers $n, k$ $(1 \le n \le 3 \times 10^6,\ 1 \le k \le 10^9)$ representing the string length and concatenation count.
• The second line contains a lowercase English string $s$ of length $n$.

The sum of $n$ across all test cases in a single input does not exceed $3 \times 10^6$.

Output Format

For each test case, output one integer representing the answer modulo $998244353$.

3
4 2
abab
1 1
a
30 1
abaababaababaababaababaababaab

20
1
128

Hint

For the first sample input, $t = s^2 = \texttt{abababab}$ contains 20 palindromic substrings.

For the third sample input, the resulting string is $(\texttt{abaab})^6$.

Constraints

This problem uses bundled tests. You must pass all test cases in a subtask to receive points.

Subtask 1 contains samples and is worth 0 points.

• Subtask 3 guarantees $\sum k \le 3 \times 10^6$.
• Subtask 4 guarantees $\sum n^2 \le 2.5 \times 10^7$.

Translated by DeepSeek R1