Problem Statement

First, a string $T$ is given.

Then, the generation process of $N$ strings $S_1,S_2,\ldots ,S_N$ is given. The generation process consists of $N$ steps, and generates strings one by one in the order from $S_1$ to $S_N$, $1$ string per $1$ step. The $i$-th step is given in one of the following forms.

• (Process A) If a non-empty string $s$ other than ~ is given, let $S_i=s$.
• (Process B) If the given string is ~, positive integers $j$ , $k$ less than $i$ are additionally given, and $S_i$ is the string obtained by concatenating $S_j$ and $S_k$ in this order.

Let $K$ be the number of contiguous parts of $S_N$ that match $T$. Output $K$ modulo $998244353$.

Constraints

The input satisfies the following constraints.

• $N$ is an integer between $1$ and $100000$, inclusive.
• The number of characters $|T|$ of $T$ is between $1$ and $50$, inclusive.
• The characters that may appear in the strings given as $s$ or $T$ are the $62$ kinds of ASCII characters consisting of lowercase English letters, uppercase English letters, and digits.
• The length of a string $s$ is at least $1$.
• The total length of the strings given as $s$ does not exceed $100000$. However, the ~ of (Process B) is not counted.
• For the $i$-th step, if it is (Process B), $1\leq j\lt i$
• For the $i$-th step, if it is (Process B), $1\leq k\lt i$

Input

The input is given in the following format.

$N$
$T$
$\text{step}_1$
$\text{step}_2$
$\vdots$
$\text{step}_N$

$\text{step}_i$ $(1\leq i\leq N)$ represents the $i$-th step. It is in one of the following $2$ forms.

$s$

~ $j$ $k$

The former indicates that $S_i$ is given directly. The latter indicates that $S_i$ is defined as the concatenation of $S_j$ and $S_k$.

Output

Output the value of $K$ modulo $998244353$, followed by a newline.

Sample

2
8Em2d
2dXXXXX8Em2dXXXXX8Em
~ 1 1

3

6
aba
aba
bbaab
b
~ 1 2
~ 4 1
~ 3 5

3

26
a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
~ 1 1
~ 2 2
~ 3 3
~ 4 4
~ 5 5
~ 6 6
~ 7 7
~ 8 8
~ 9 9
~ 10 10
~ 11 11
~ 12 12
~ 13 13
~ 14 14
~ 15 15
~ 16 16
~ 17 17
~ 18 18
~ 19 19
~ 20 20
~ 21 21
~ 22 22
~ 23 23
~ 24 24
~ 25 25

679477247