蓝桥杯2024年第十五届决赛真题-重复的串

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

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

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

aba 6

53

【评测用例规模与约定】

对于 40% 的评测用例，n ≤ 20，|S | ≤ 6 ；

另有 10% 的评测用例，n ≤ 500，|S | ≤ 2 ；

对于 70% 的评测用例，n ≤ 10⁵ ；

对于所有评测用例，1 ≤ n ≤ 10⁹，1 ≤ |S | ≤ 30 。