题目背景

给定字符串 $T$ 和 $S$ 。有个空字符 $A$ ，每次可以把 $S$ 的首字母插入 $A$ 的开头或者结尾后删除，最多操作|S|次。有多少种方案使得 $T$ 是 $A$ 的前缀？

题目描述

奆有一个长度为 $m$ 的字符串 $T$ ，所有前缀为 $T$ 的字符串都是魔咒。

奆还有一个长度为 $n$ 的字符串 $S$ 和一个空字符串 $A$ 。

在占卜过程中，奆需要执行一系列操作。有以下两种：

• 删除 $S$ 的第一个字符，并将其添加到 $A$ 的最前面。
• 删除 $S$ 的第一个字符，并将其添加到 $A$ 的最后面。

奆可以进行的操作不超过 $n$ 次。为了完成占卜，她想知道将 $A$ 变为魔咒(即前缀为 $T$ ) 的操作方案数。请计算答案对 $998244353$ 取模的结果。

输入格式

第一行输入一个长度为 $n$ 的字符串 $S$ ( $1≤n≤3000$ )。

第二行输入长度为 $m$ ( $1≤m≤n$ ) 的字符串 $T$ 。

这两个字符串都只包含小写字母。

输出格式

输出方案数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

abab
ba

输出 #1

12

输入输出样例 #2

输入 #2

rotator
rotator

输出 #2

4

输入输出样例 #3

输入 #3

cacdcdbbbb
bdcaccdbbb

输出 #3

24

说明/提示

对于$40\%$的数据：$1\le n \le 100$

对于$100\%$的数据：$1\le n\le 3000$