D. Double Subsequence
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Little L has a hard time seeing strings he doesn't like! Seeing them appear as subsequences is too!

Given a long string $$$S$$$ denoting the text that Little L wants to read, and exactly two short strings $$$s_1$$$, $$$s_2$$$ denoting the strings that Little L doesn't want to see, all three strings consist of lowercase letters.

Little L is disgusted by the fact that two strings appear as subsequences within the text at the same time, and he believes that a string $$$T$$$'s antisense value is 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's going to read each subsegment of $$$S$$$, he now needs you to find the sum of the antisense value of all the subsegments of $$$S$$$. Since the answer may be too large, you only need to output the result of modeling $$$998244353$$$.

A sequence $$$H$$$ is a subsequence of a sequence $$$T$$$ if $$$H$$$ can be obtained from $$$T$$$ by the deletion of several (possibly zero or all) elements.

A sequence $$$H$$$ is a subsegment of a sequence $$$T$$$ if $$$H$$$ can be obtained from $$$T$$$ by the deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

Input

The input consists of three lines, each line a string consisting only of lowercase letters.

The string in the first line represents $$$S$$$, the second line represents $$$s_1$$$, and the third line represents $$$s_2$$$, where $$$1\le |S|\le 1\times 10^5$$$, $$$1\le |s_1|$$$, $$$|s_2|\le 20$$$.

Output

Outputs an integer representing the answer solved.

Example
Input
iccpcicpc
icpc
ccpc
Output
133
Note

The example is explained as follows:

begin positionend positionicpc numbersccpc numbers
1521
1621
1742
1842
19119
2501
2601
2702
2802
2919
3913
4911
5911
6910

In the remaining subsegments, both strings appear as subsequences $$$0$$$ times.

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