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