结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某物流园区的立体仓库占地方正，内部的巡检通道可以抽象为 $n$ 行 $m$ 列的网格，行从上到下编号 $1$ 到 $n$，列从左到右编号 $1$ 到 $m$。巡检机器人每天从西北角的格子 $(1,1)$ 出发，前往东南角的格子 $(n,m)$ 完成例行巡检。受货架布局限制，机器人每一步只能向右或向下移动一格，即只能从格子 $(i,j)$ 走到 $(i,j+1)$ 或 $(i+1,j)$，且全程不得走出网格。

消防验收规程要求，仓库中若干行被整行的防火卷帘彻底封死，这样的行称为封闭行。每道卷帘上开有若干门格供巡检通行：在封闭行上，只有门格可以通行，机器人无论从上方进入该行、在该行上向右移动，还是从该行继续向下，落脚点都必须是门格；封闭行上的其余格子一律不能停留。非封闭行上没有限制，按前述移动规则正常通行。

园区管理处要核算巡检路线的调度余量，需要知道在当前卷帘与门格布置下，机器人从 $(1,1)$ 到 $(n,m)$ 一共有多少条不同的合法路径。两条路径不同，当且仅当它们经过的格子序列不同。由于答案可能很大，请输出路径数对 $998244353$ 取模的结果。

数据保证：若第 $1$ 行是封闭行，则 $(1,1)$ 必为门格；若第 $n$ 行是封闭行，则 $(n,m)$ 必为门格。

输入格式

从文件 maze.in 中读入数据。

• 第一行三个整数 $n, m, w$，依次表示网格行数、列数与封闭行的数量；
• 接下来 $w$ 行，每行描述一道卷帘：先两个整数 $r, c$，表示第 $r$ 行是封闭行、该行共有 $c$ 个门格；随后 $c$ 个整数，按升序给出各门格所在的列号。

输出格式

输出到文件 maze.out 中。

输出一行一个整数，表示合法路径数对 $998244353$ 取模的结果。

样例

3 3 0

6

样例 1 解释

把向右一步记为 R、向下一步记为 D。从 $(1,1)$ 到 $(3,3)$ 恰好需要两步 R 与两步 D，逐条列出全部走法：RRDD、RDRD、RDDR、DRRD、DRDR、DDRR，共 $6$ 条。

4 5 1
3 1 3

3

样例 2 解释

第 $3$ 行是封闭行，只有格子 $(3,3)$ 是门格，因此任何合法路径都必须先到达 $(2,3)$，再向下进入 $(3,3)$。从 $(1,1)$ 到 $(2,3)$ 的走法有 $3$ 条：RDD、DRD、DDR。进入 $(3,3)$ 后不能在该行右移——$(3,4)$ 不是门格——只能向下到 $(4,3)$，再连续向右两格到达 $(4,5)$，这一段只有 $1$ 条走法。合计 $3$ 条。

5 5 2
2 2 2 3
4 2 3 4

9

样例 3 解释

第 $2$ 行卷帘的门在列 $2$、$3$，第 $4$ 行卷帘的门在列 $3$、$4$。以到达几个关键位置的走法数计：到达 $(2,2)$、$(2,3)$ 各 $1$ 种；从这两个门向后走，到达 $(4,3)$ 的有 $3$ 种，到达 $(4,4)$ 的有 $6$ 种；从第 $4$ 行的两个门到达 $(5,5)$ 各 $1$ 种。合计 $3 + 6 = 9$ 种。

数据范围

对于所有测试数据，保证：

• $1 \le n, m \le 10^6$；
• $0 \le w \le 200$，各封闭行的行号互不相同，门格总数不超过 $4000$；
• 每个门格列号 $c$ 满足 $1 \le c \le m$，同一封闭行内门格列号互不相同且按升序给出；
• 若第 $1$ 行是封闭行，则 $(1,1)$ 必为门格；若第 $n$ 行是封闭行，则 $(n,m)$ 必为门格。

各测试点的约束如下：

• 特殊性质 A：至多只有一行是封闭行。
• 特殊性质 B：每道卷帘恰好只开一个门格。