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

N/A

N/A

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