P10581 [Lanqiao Cup 2024 National A] Repeated String

Given a string $S$ consisting only of lowercase letters, ask how many strings of length $n$ consisting only of lowercase letters contain $S$ exactly twice. Output the answer modulo $998\ 244\ 353$.

Input one line containing a string $S$ and an integer $n$, separated by a space.

Output one line containing one integer representing the answer.

For $40\%$ of the test cases, $n \le 20$ and $|S| \le 6$. For another $10\%$ of the test cases, $n \le 500$ and $|S| \le 2$. For $70\%$ of the test cases, $n \le 10^5$. For all test cases, $1 \le n \le 10^9$ and $1 \le |S| \le 30$. Translated by ChatGPT 5