#P2022C. Protect the Second Best KK in the World

Protect the Second Best KK in the World

Protect the second best kk in the world

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

As an individual trainee who has been practicing algorithm for 2.5 years(Almost 3 years actually), Ckk has become the second best Kunkun in the world. Unlike the best Kunkun in the world, the second best Kunkun doesn't like C\textbf{C}hang(Sing), T\textbf{T}iao(Dance), R\textbf{R}ap, L\textbf{L}anqiu(Basketball), but he can really Ctrl + C\textbf{Ctrl + C}(copy) and Ctrl + V\textbf{Ctrl + V}(paste) someone people's code.

One day, Ckk gets nn basic strings pip_i and a target string ss and he needs to build the target string with these basic strings using copy and paste which is easy for him. However, he wants to know how many copy and paste ways to build the target string. This is difficult for a 2.5 years algorithm trainee, so he asks you, a clever ikun for help.

More precisely, you have to calculate how many ways to build the target string ss out of the basic strings by concatenating them. You can use the basic strings any number of times and in any order.

Specially, two ways to build the target string are considered different, if and only if there is a position that you choose different basic strings. It is promised there aren't same strings among the basic strings.

Since the answer may be very large, you only need to output the result modulo 998244353998244353.

Input

The first line contains one integers n(1n200)n(1\leq n\leq 200) denoting the number of basic string.

The second line contains one integers denoting the length of target string s(1s105)|s| (1 \leq |s| \leq 10^5) and the string ss.

The next nn lines contain the length of each basic string pi(1pi105)|p_i|(1 \leq |p_i| \leq 10^5) and the string pip_i.

It's guaranteed that the total length of all strings in all test cases does not exceed 21062 * 10^6.

Output

Print a single integer, denoting the answer to the question, modulo 998244353998244353.

3 
6 abbabb
1 a
1 b
2 ab
4
1
5 aaaab
1 a
0
6
30 abbabbabbbabaababbaaaababbbaba
1 a
1 b
2 ab
2 ba
3 aab
3 aba
72576

Notes

In the first Sample, we have 4 ways to build the string:

1.abbabb = a + b + b + a + b + b 2.abbabb = ab + b + a + b + b 3.abbabb = a + b + b + ab + b 4.abbabb = ab + b + ab + b