← 返回题目列表

Codeforces · 1336/C

C. 卡维和魔法咒语

中文机器翻译题面 查看原题

卡维,神秘的算命先生,深信一个人的命运是不可避免的,无法避免的。当然,她靠预测别人的未来谋生。在占卜时,卡维相信魔法咒语可以为她提供预知未来的强大力量。

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$$$ 的子字符串,出现在 $$$S$$$ 的开头。

输入

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

第二行包含长度为 $$$m$$$ 的字符串 $$$T$$$ ($$$1 \leq m \leq n$$$)。

两个字符串仅包含小写拉丁字母。

输出

输出仅包含一个整数 - 答案以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

abab
ba

输出 #1

12

输入 #2

defineintlonglong
signedmain

输出 #2

0

输入 #3

rotator
rotator

输出 #3

4

输入#4

cacdcdbbbb
bdcaccdbbb

输出#4

24

注意

第一次测试:

红色的是魔法咒语。在第一个操作中,Kaavi 可以在 $$$A$$$ 的前面或后面添加第一个字符“a”,虽然结果相同,但它们被视为不同的操作。所以答案是$$$6\times2=12$$$。