G. Keyword
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Moriarty has picked up Sherlock's trail and managed to obtain data about an important event that will occur exactly when a specific high-frequency radio signal transmits the string $$$S$$$.

However, this time Sherlock managed to confuse his main enemy, and he deliberately sent Moriarty this information. Instead of useful data, he will send one of the characters from his encoding alphabet uniformly at random every second. During this time, Moriarty will wait until the substring equal to $$$S$$$ appears in the stream of received characters; after that, he will immediately stop his observations.

Sherlock is very busy right now, so he asked you to determine the expected number of seconds that Moriarty will observe until the string $$$S$$$ appears in the stream. Output the answer modulo $$$998244353$$$.

Input

The first line contains the string $$$A$$$ ($$$1 \le |A| \le 36$$$), consisting of lowercase Latin letters or digits, which represents the set of characters that Sherlock will send uniformly at random. It is guaranteed that all characters in $$$A$$$ are distinct.

The second line contains the string $$$S$$$ ($$$1 \le |S| \le 5 \cdot 10^5$$$), which is the sequence of characters that Moriarty will wait for. It is guaranteed that all characters in $$$S$$$ are among the characters in string $$$A$$$.

Output

In a single line, output the expected number of seconds that Moriarty will wait, modulo $$$998244353$$$.

Examples
Input
01
1
Output
2
Input
abo
aboba
Output
246
Input
andrew13
andrew13
Output
16777216