P11749 「TPOI-1C」Standard Problem.

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$.

**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$.

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

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 | Points | $n \le$ | $k \le$ | | :-----: | :----: | :-----------: | :-----------: | | 2 | 5 | 2 | $10^9$ | | 3 | 30 | $3 \times 10^6$ | $3 \times 10^6$ | | 4 | 30 | 2000 | $10^9$ | | 5 | 35 | $3 \times 10^6$ | $10^9$ | - 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