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. [Image] 

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$.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
abab
ba

Output
12
Input
defineintlonglong
signedmain

Output
0
Input
rotator
rotator

Output
4
Input
cacdcdbbbb
bdcaccdbbb

Output
24


-----Note-----

The first test:

$\text{baba abab bbaa baab baab}$

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$.

Difficulty: interview

Starter code:

Solutions:
S = input()
T = input()
base = 998244353
dp = [[0 for _ in range(len(S) + 1)] for _ in range(len(S) + 1)]
for j in range(1, len(S) + 1):
    if (j > len(T)) or (S[0] == T[j - 1]):
        dp[1][j] = 2
for i in range(2, len(S) + 1):
    for j in range(1, len(S) - i + 1 + 1):
        if (j > len(T)) or (S[i - 1] == T[j - 1]):
            dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % base
        if (j + i - 1 > len(T)) or (S[i - 1] == T[j + i - 1 - 1]):
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % base
ans = 0
for i in range(len(T), len(S) + 1):
    ans = (ans + dp[i][1]) % base
print(ans)

import sys
readline = sys.stdin.readline

S = input()
T = '*' + input()
n, m = len(S), len(T)
mod = 998244353
dp = [[0]*(n+5) for _ in range(n+5)]
for i in range(n+1):
    dp[i][i+1] = 1

for i, c in enumerate(S, start=1):
    for l, r in zip(list(range(0, n+1)), list(range(i, n+2))):
        if l >= m or 0 < l and T[l] == c:
            dp[l-1][r] += dp[l][r] % mod
        if r >= m or T[r] == c:
            dp[l][r+1] += dp[l][r] % mod

print(sum(dp[0][m:]) % mod)


import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    s = SI()
    t = SI()
    sn = len(s)
    tn = len(t)
    # dp[i][j]...sをi番目までみたときのt[j:j+i]の作り方
    dp = [[0] * sn for _ in range(sn + 1)]
    for j in range(sn): dp[1][j] = 2 if j >= tn or t[j] == s[0] else 0
    for i, c in enumerate(s[1:], 1):
        for j in range(sn):
            pre = dp[i][j]
            if pre == 0: continue
            # 左に追加する場合
            if j > 0 and (j - 1 >= tn or t[j - 1] == c):
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + pre) % md
            # 右に追加する場合
            if j + i < sn and (j + i >= tn or t[j + i] == c):
                dp[i + 1][j] = (dp[i + 1][j] + pre) % md
    ans = sum(dp[i][0] for i in range(tn, sn + 1)) % md
    print(ans)

main()