A. Almost Prefix Concatenation
time limit per test
3 с
memory limit per test
512 megabytes
input
standard input
output
standard output

A string $$$A = a_1 a_2 \cdots a_n$$$ of length $$$n$$$ is a concatenation of $$$n$$$ characters $$$a_1, a_2, \ldots, a_n$$$, and its length is denoted by $$$|A|$$$. Similarly, the concatenation of two strings $$$A = a_1 a_2 \cdots a_n$$$ and $$$B = b_1 b_2 \cdots b_m$$$ is $$$a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m$$$, denoted by $$$A + B$$$.

The edit distance between two strings $$$A = a_1 a_2 \cdots a_n$$$ and $$$B = b_1 b_2 \cdots b_n$$$ of the same length $$$n$$$ is the number of indices $$$i$$$ such that $$$a_i \neq b_i$$$.

We call the string $$$A$$$ formed by the first $$$k$$$ characters of another string $$$B$$$ ($$$k \leq |B|$$$) as the $$$k$$$-th prefix of $$$B$$$, and a string $$$P$$$ as an almost prefix of another string $$$Q$$$ if $$$|P| \leq |Q|$$$ and the edit distance between $$$P$$$ and the $$$|P|$$$-th prefix of $$$Q$$$ is at most $$$1$$$.

Given two strings $$$S$$$ and $$$T$$$ consisting of lowercase English letters, you are asked to find all ways to split $$$S$$$ into many parts such that each part is a non-empty almost prefix of string $$$T$$$, and then report the sum of the squared number of parts of all ways in modulo $$$998244353$$$. More formally, let $$$S = P_1 + P_2 + \ldots + P_n$$$ be a possible way, you are asked to calculate $$$$$$\left(\sum_{\substack{S = P_1 + P_2 + \ldots + P_n \\ \forall_{i=1, 2, \ldots, n} P_i\text{ is an almost prefix of }T}}{n^2}\right) \bmod 998\,244\,353\text{.}$$$$$$

Input

The first line of the input contains a string $$$S$$$ ($$$1 \leq |S| \leq 1\,000\,000$$$), consisting of only lowercase English letters.

The next line contains a string $$$T$$$ ($$$1 \leq |T| \leq 1\,000\,000$$$), consisting of only lowercase English letters.

Output

Print a single line containing a single integer: the sum of the squared number of parts of all ways in modulo $$$998\,244\,353$$$.

Examples
Input
ababaab
aba
Output
473
Input
ac
ccpc
Output
5
Note

In the first sample case ($$$S = \texttt{ababaab}$$$, $$$T = \texttt{aba}$$$), there are $$$19$$$ ways to split:

  • $$$1$$$ way of $$$3$$$ parts, which is $$$\texttt{ab} + \texttt{aba} + \texttt{ab}$$$;
  • $$$6$$$ ways of $$$4$$$ parts, such as $$$\texttt{a} + \texttt{b} + \texttt{aba} + \texttt{ab}$$$;
  • $$$7$$$ ways of $$$5$$$ parts, such as $$$\texttt{a} + \texttt{b} + \texttt{ab} + \texttt{a} + \texttt{ab}$$$;
  • $$$4$$$ ways of $$$6$$$ parts, such as $$$\texttt{a} + \texttt{b} + \texttt{a} + \texttt{b} + \texttt{a} + \texttt{ab}$$$;
  • $$$1$$$ way of $$$7$$$ parts, which is $$$\texttt{a} + \texttt{b} + \texttt{a} + \texttt{b} + \texttt{a} + \texttt{a} + \texttt{b}$$$.

Therefore, the result for the first sample case is $$$(3^2 + 6 \times 4^2 + 7 \times 5^2 + 4 \times 6^2 + 7^2) \bmod 998244353 = 473$$$.