题目描述

你手上有 $n+m$ 个石子，有 $n$ 个普通的石子和 $m$ 个特殊的石子。

这 $n+m$ 个石子共有 $c+1$ 种颜色，其中 $m$ 个特殊的石子的颜色为 $c+1$，其余石子的颜色为 $1\sim c$ 中的一种。

已知第 $i$ 种颜色的石子有 $a_i$ 个，保证 $\sum_{i=1}^c a_i=n$。

你将这些石子摆成一行，你决定观察你摆的石子的美观度。

为了方便观察，美观度由最左边和最右边的石子决定，具体如下：

• 找到最左边的特殊的石子，记其为从左到右的第 $x$ 个石子。

• 考虑最右边的石子，如果是普通石子，则找到这个石子左边第一个颜色不同的石子（可以是特殊石子），记其右边的石子数为 $y$。

例如，有 $5$ 个石子，从左到右颜色依次为 $2,3,3,1,1$，其中颜色 $1,2$ 为普通石子，颜色 $3$ 为特殊石子。

最左边的特殊石子是从左到右第 $2$ 个石子，所以 $x=2$。

最右边的石子颜色是 $1$，是一个普通石子，左边第一个颜色不同的石子是从左到右第 $3$ 个石子，它的右边有 $2$ 个石子，所以 $y=2$。

序列的美观度定义如下：

• 如果最右边的石子是特殊的石子，则美观度为 $w_x$。
• 否则，记最右边的石子颜色为 $u$，则美观度为 $w_x\times v_{u,y}$。

其中 $w$ 和 $v$ 由题目给定。

现在你想知道，所有不同的石子序列，美观度之和是多少？

两个序列不同当且仅当至少有一个位置的石子颜色不同，答案对 $998244353$ 取模。

输入格式

从文件 sand.in 中读入。

第一行 $3$ 个数，表示 $n,m,c$。

第二行 $n+1$ 个数，表示 $w_1\sim w_{n+1}$。

第三行 $c$ 个数，表示每种颜色的石子个数。

接下来 $c$ 行，第 $i$ 行 $a_i$ 个数，表示 $v_{i,1}\sim v_{i,a_i}$。

输出格式

输出到文件 sand.out 中。

输出一行一个整数，表示所有不同的石子序列的美观度之和对 $998244353$ 取模的结果。

样例

样例输入 1

2 1 1
2 3 4
2
2 3

样例输出 1

16

样例解释 1

共有 $3$ 种可能序列。

$\{1,1,2\}$，$x=3$，最右边是特殊石子，美观度为 $w_3=4$。

$\{1,2,1\}$，$x=2,y=1$，美观度为 $w_2\times v_{1,1}=3\times 2=6$。

$\{2,1,1\}$，$x=1,y=2$，美观度为 $w_1\times v_{1,2}=2\times 3=6$。

总和为 $4+6+6=16$。

样例输入 2

8 2 6
923945407 493986782 501032365 554208540 820758204 352305609 320140120 118497648 467798137 
3 1 1 1 1 1 
297408812 522217066 885036796 
441963214 
132614765 
507229015 
950047419 
634968424 

样例输出 2

734049932

样例 3

见选手目录下的 sand/sand3.in 与 sand/sand3.ans。

这个样例满足测试点 $6\sim 7$ 的约束条件。

样例 4

见选手目录下的 sand/sand4.in 与 sand/sand4.ans。

这个样例满足测试点 $8\sim 10$ 的约束条件。

样例 5

见选手目录下的 sand/sand5.in 与 sand/sand5.ans。

这个样例满足测试点 $16\sim 17$ 的约束条件。

样例 6

见选手目录下的 sand/sand6.in 与 sand/sand6.ans。

这个样例满足测试点 $18\sim 19$ 的约束条件。

样例 7

见选手目录下的 sand/sand7.in 与 sand/sand7.ans。

这个样例满足测试点 $20\sim 22$ 的约束条件。

数据范围

对于 $100$ 的数据，$1\le c\le n\le 2\times 10^5$，$1\le m\le 30$，$a_i\ge 1$，$\sum_{i=1}^c a_i=n$，$0\le w,v\lt 998244353$。

测试点编号	$n$	$m$	特殊限制
$1,2$	$\le 10$		$n+m\le 10$
$3$	$\le 2\times10^5$	$=1$	$c=1$
$4,5$	$\le 2\times 10^5$		无
$6,7$		$\le 30$	$c=1$
$8,9,10$	$\le 200$		无
$11,12,13,14$	$\le 2000$
$15$	$\le 2\times 10^5$		保证 $v_{i,j}=1,w_i=1$
$16,17$			保证 $w_i=1$
$18,19$			保证 $v_{i,j}=1$
$20,21,22$		$=2$	无
$23,24,25$		$\le 30$