CF1336C Kaavi and Magic Spell

Kaavi 是一位神秘的占卜师，她坚信命运是不可避免且无法逃避的。当然，她以预测他人的未来为生。在进行占卜时，Kaavi 相信魔法咒语能够赋予她强大的力量来预见未来。  Kaavi 有一个长度为 $m$ 的字符串 $T$，所有以 $T$ 为前缀的字符串都是魔法咒语。Kaavi 还有一个长度为 $n$ 的字符串 $S$ 和一个空字符串 $A$。 在占卜过程中，Kaavi 需要执行一系列操作。有两种不同的操作： - 删除 $S$ 的第一个字符，并将其添加到 $A$ 的开头。 - 删除 $S$ 的第一个字符，并将其添加到 $A$ 的末尾。 Kaavi 最多可以执行 $n$ 次操作。为了完成占卜，她想知道有多少种不同的操作序列可以使 $A$ 成为一个魔法咒语（即以 $T$ 为前缀）。作为她的助手，你能帮她计算吗？答案可能很大，所以 Kaavi 只需要知道答案对 $998\,244\,353$ 取模后的结果。 如果两个操作序列长度不同，或者存在某个 $i$ 使得它们的第 $i$ 次操作不同，则认为这两个操作序列不同。 子串是字符串中连续的一段字符。一个字符串 $S$ 的前缀是 $S$ 开头的一个子串。

第一行包含一个长度为 $n$ 的字符串 $S$（$1 \leq n \leq 3000$）。 第二行包含一个长度为 $m$ 的字符串 $T$（$1 \leq m \leq n$）。 两个字符串均只包含小写拉丁字母。

输出一个整数，表示答案对 $998\,244\,353$ 取模后的结果。

第一个测试样例：  红色部分是魔法咒语。在第一次操作时，Kaavi 可以选择将第一个字符 "a" 添加到 $A$ 的开头或末尾，尽管结果相同，但它们被视为不同的操作。因此答案是 $6\times2=12$。 由 ChatGPT 4.1 翻译