P10581 [蓝桥杯 2024 国 A] 重复的串

给定一个仅含小写字母的字符串 $S$，问有多少个长度为 $n$ 的仅含小写字母的字符串中恰好出现了两次 $S$。答案对 $998\ 244\ 353$ 取模。

输入一行包含一个字符串 $S$ 和一个整数 $n$，用一个空格分隔。

输出一行包含一个整数表示答案。

对于 $40\%$ 的评测用例，$n \le 20$，$|S| \le 6$； 另有 $10\%$ 的评测用例，$n\le 500$，$|S| \le 2$； 对于 $70\%$ 的评测用例，$n\le 10^5$； 对于所有评测用例，$1\le n\le 10^9$，$1 \le |S| \le 30$。