该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

cyh 最近在游戏中学会了一个超级大招——灭世雷霆！

释放这个技能需要进行一段咒语吟唱，这段咒语是一个长度为 $n$ 的字符串 $S$

cyh 的吟唱过程分为 $m$ 个部分，第 $i$ 个部分有 $k_i$ 种不同的吟唱方式可以选择，每种吟唱方式都是一个由小写字母组成的字符串

cyh 现在找到一种可以便捷释放技能的方法：

也就是在灭世雷霆的咒语上找到 $m$ 个互不相交的子串:$[x_1,y_1],[x_2,y_2] \dots [x_m,y_m]$，满足任意一个子串 $[x_i,y_i]$ 是第 $i$ 部分的吟唱方式之一，并且 $x_i \leq y_i < x_{i+1}$

这里我们认为两种吟唱方案只要存在任意的 $i$ 使得 $x1_i != x2_i$ 或者 $y1_i != y2_i$，则这两种吟唱方案是不同的

现在 cyh 想知道，自己有多少种不同的吟唱方案可以释放出灭世雷霆？

这个方案数可能会很大，所以方案数只要对 $998244353$ 取模即可

输入格式

第一行包含两个整数 $n,m$，含义如题 第二行包含 $n$ 个用空格隔开的字符，表示字符串 $S$ 接下来 $m$ 行，每行第一个整数 $k_i$ 表示第 $i$ 个吟唱部分有 $k_i$ 种吟唱方式 接下来 $k_i$ 个用空格隔开的字符串表示每一种吟唱方式

输出格式

输出一个整数目标吟唱方案的数量，由于答案可能会很大，请将答案对 $998244353$ 取模

数据范围

以下用 $len$ 表示吟唱方式的长度 对于 $100\%$ 的数据： $n \leq 10^5, m \leq 50, \sum{k_i} \leq 100, k_i \leq 5, len \leq 10$ 其中： 对于 $15\%$ 的数据： $k_i = 1$ 另有 $35\%$ 的数据： $m == 1$ 另有 $10\%$ 的数据： $len == 1$ 另有 $10\%$ 的数据： $len \leq 2$

特别的保证：保证吟唱的每个部分不存在相同的吟唱方式，并且只存在小写字母

样例输入

11 3
x l s a k c s p n o i
1 xls
1 ak
2 csp noi

样例输出

2

样例解释

有两种方案能够释放技能：[xls-ak-csp] 和 [xls-ak-noi]