limpid and S-chan are transmitting a secret message, which can be viewed as a number $x$. S-chan decides to encode the secret message $x$ into a string $S$. limpid decides to decrypt what this $x$ is. After knowing $S$, he will restore it to the actual decoded string $S'_n$ (where $n$ is the length of string $S$, i.e., $|S|$). The specific restoration method is:

$$S'_i = \begin{cases} S'_{i-1} + a_i + S'_{i-1} & \text{if } i > 1 \\ a_1 & \text{if } i = 1 \end{cases}$$

where $a_i$ represents the character at the $i$-th position of string $S$ (indexed from 1), and the plus sign denotes the concatenation operation. After knowing the actual decoded string, limpid will start decrypting based on a string $T$ previously agreed upon with S-chan, where $x$ is the number of times $T$ appears as a subsequence in $S'_n$. If you are limpid, given $S$ and $T$, can you help him decrypt and obtain the secret message $x$? Since the answer may be very large, you only need to output the value of $x$ modulo $998\,244\,353$.

Input

The first line contains two strings $S, T$ ($1 \le |S|, |T| \le 100$). It is guaranteed that both strings contain only lowercase English letters.

Output

Output an integer representing the value of $x$ modulo $998\,244\,353$.

Examples

Input 1

aba ba

Output 1

5