Problem Description

Little L feels very uncomfortable when he sees strings he dislikes. He also feels uncomfortable when he sees them appear as subsequences.

Given a long string $S$ representing the text that Little L needs to read, and exactly two short strings $s_1$, $s_2$ representing the strings that Little L does not want to see. All three strings consist of lowercase letters.

Little L strongly dislikes having both of these strings appear in the text as subsequences at the same time. He defines the discomfort value of a string $T$ as: the product of the number of occurrences of $s_1$ as a subsequence of $T$ and the number of occurrences of $s_2$ as a subsequence of $T$.

Since he will read every substring of $S$, you now need to compute the sum of the discomfort values of all substrings of $S$. Since the answer may be too large, you only need to output the result modulo $998244353$.

A string $H$ is a substring of $T$ if and only if $H$ can be obtained by deleting some characters from the beginning of $T$ and some characters from the end of $T$ (you may delete zero characters from the prefix/suffix, or delete the entire string to obtain the empty string).

A string $H$ is a subsequence of $T$ if and only if $H$ can be obtained by deleting some characters from $T$ (you may delete zero characters, or delete all characters to obtain the empty subsequence).

Input Format

The input consists of three lines, each containing a string of lowercase letters.

The first line is $S$, the second line is $s_1$, and the third line is $s_2$. Here, $1\le |S|\le 1\times 10^5$, $1\le |s_1|,|s_2|\le 20$.

Output Format

Output a single integer representing the computed answer.

iccpcicpc
icpc
ccpc

133

Hint

In all other substrings, the numbers of occurrences of the two strings as subsequences are both $0$.

The answer is $(2\times 1) \times 2 + (4\times 2) \times 2 + 11\times 9 + (0\times 1)\times 2 + (0\times 2)\times 2 + 1\times 9 + 1\times 3 + (1\times 1)\times 2 + 1\times 0=133$.

Translated by ChatGPT 5