問題文

始めに文字列 $T$ が与えられます。

その後、 $N$ 個の文字列 $S_1,S_2,\ldots ,S_N$ の生成過程が与えられます。 生成過程は $N$ ステップからなり、$S_1$ から $S_N$ の順に $1$ ステップにつき $1$ 個ずつ文字列を生成します。 $i$ 番目のステップは次のいずれかの形式で与えられます。

• (過程A) ~ 以外の空でない文字列 $s$ が与えられた場合、 $S_i=s$ とする。
• (過程B) 与えられた文字列が ~ であった場合、追加で $i$ 未満の正整数 $j$ , $k$ が与えられるので、 $S_i$ は $S_j$ と $S_k$ をこの順に連結した文字列とする。

$S_N$ の連続する部分であって $T$ に一致するものの個数を $K$ とします。 $K$ を $998244353$ で割った余りを出力してください。

制約

入力は次の制約を満たします。

• $N$ は $1$ 以上 $100000$ 以下の整数である。
• $T$ の文字数 $|T|$ は $1$ 以上 $50$ 以下である。
• $s$ や $T$ として与えられる文字列に含まれうる文字は、 ASCII 文字のうち、英小文字、英大文字、数字の合計 $62$ 種である。
• 文字列 $s$ の長さは $1$ 以上である。
• $s$ として与えられる文字列の長さの合計は $100000$ を超えない。ただし (過程B) の ~ は数えない。
• $i$ 番目のステップについて、それが (過程B) である場合、 $1\leq j\lt i$
• $i$ 番目のステップについて、それが (過程B) である場合、 $1\leq k\lt i$

入力

入力は次の形式で与えられます。

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

$\text{step}_i$ $(1\leq i\leq N)$ は $i$ 番目のステップを表します。次の $2$ 通りの形式のいずれかです。

$s$

~ $j$ $k$

前者は $S_i$ が直接与えられることを表します。後者は $S_i$ が $S_j$ と $S_k$ の連結で定義されることを表します。

出力

$K$ の値を $998244353$ で割った余りを出力したのち、改行してください。

サンプル

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