CF1336C.Kaavi and Magic Spell

Kaavi, the mysterious fortune teller, deeply believes that one's fate is inevitable and unavoidable. Of course, she makes her living by predicting others' future. While doing divination, Kaavi believes that magic spells can provide great power for her to see the future.

Kaavi has a string $T$ of length $m$ and all the strings with the prefix $T$ are magic spells. Kaavi also has a string $S$ of length $n$ and an empty string $A$.

During the divination, Kaavi needs to perform a sequence of operations. There are two different operations:

• Delete the first character of $S$ and add it at the front of $A$.
• Delete the first character of $S$ and add it at the back of $A$.

Kaavi can perform no more than $n$ operations. To finish the divination, she wants to know the number of different operation sequences to make $A$ a magic spell (i.e. with the prefix $T$). As her assistant, can you help her? The answer might be huge, so Kaavi only needs to know the answer modulo $998\,244\,353$.

Two operation sequences are considered different if they are different in length or there exists an $i$ that their $i$-th operation is different.

A substring is a contiguous sequence of characters within a string. A prefix of a string $S$ is a substring of $S$ that occurs at the beginning of $S$.

神秘的占卜师凯薇深信，人的命运是注定且不可改变的。当然，她靠预测他人的未来谋生。在占卜过程中，凯薇相信魔法咒语能赋予她强大的力量，从而窥见未来。

凯薇拥有一个长度为 $m$ 的字符串 $T$，所有以 $T$ 为前缀的字符串均被视为魔法咒语。此外，她还有一个长度为 $n$ 的字符串 $S$ 和一个空字符串 $A$。

在占卜过程中，凯薇需执行一系列操作。共有两种不同的操作：

• 删除 $S$ 的首字符，并将其添加到 $A$ 的前端；
• 删除 $S$ 的首字符，并将其添加到 $A$ 的尾端。

凯薇最多可执行 $n$ 次操作。为了完成占卜，她想知道：有多少种不同的操作序列，能使最终得到的 $A$ 成为一个魔法咒语（即 $A$ 以 $T$ 为前缀）？作为她的助手，你能帮她解决这个问题吗？答案可能非常大，因此凯薇只需要知道答案对 $998\,244\,353$ 取模的结果。

若两个操作序列长度不同，或存在某个位置 $i$ 使得它们的第 $i$ 次操作不同，则认为这两个操作序列不同。

子串是指字符串中连续的一段字符序列。字符串 $S$ 的前缀是指出现在 $S$ 开头位置的子串。

The first line contains a string $S$ of length $n$ ($1 \leq n \leq 3000$).

The second line contains a string $T$ of length $m$ ($1 \leq m \leq n$).

Both strings contain only lowercase Latin letters.

第一行包含一个长度为 $n$ 的字符串 $S$（$1 \leq n \leq 3000$）。

第二行包含一个长度为 $m$ 的字符串 $T$（$1 \leq m \leq n$）。

两个字符串均仅由小写拉丁字母组成。

The output contains only one integer — the answer modulo $998\,244\,353$.

输出仅包含一个整数——答案对 $998\,244\,353$ 取模的结果。

The first test:

The red ones are the magic spells. In the first operation, Kaavi can either add the first character "a" at the front or the back of $A$, although the results are the same, they are considered as different operations. So the answer is $6\times2=12$.

第一次测试：

红色部分为魔法咒语。在第一次操作中，Kaavi 可以将第一个字符 “a” 添加到 $A$ 的前端或后端；尽管两种操作的结果相同，但仍被视为不同的操作。因此答案为 $6\times2=12$。