题目描述

小 L 有一个有向图，图中的顶点可以分为 $k$ 层，第 $i$ 层有 $n_i$ 个顶点，第 $1$ 层与第 $k$ 层顶点数相同，即 $n_1=n_k$，且对于第 $j$（$2\le j\le k-1$）层，$n_1\le n_j\le 2n_1$。对于第 $j$（$1\le j < k$）层的顶点，以它们为起点的边只会连向第 $j + 1$ 层的顶点。没有边连向第 $1$ 层的顶点，第 $k$ 层的顶点不会向其他顶点连边。

现在小 L 要从这个图中选出 $n_1$ 条路径，每条路径以第 $1$ 层顶点为起点，第 $k$ 层顶点为终点，并要求图中的每个顶点至多出现在一条路径中。更具体地，把每一层顶点按照 $1, 2, \dots, n_i$ 进行编号，则每条路径可以写成一个 $k$ 元组（$p_1,p_2,\dots,p_k$），表示这条路径依次经过第 $j$ 层的 $p_j$（$1\le p_j\le n_j$）号顶点，并且第 $j$（$1\le j<k$）层的 $p_j$ 号顶点有一条边连向第 $j + 1$ 层的 $p_{j+1}$ 号顶点。

小nL 把这些路径画在了纸上，发现它们会产生若干个交点。对于两条路径 $P, Q$，分别设它们在第 $j$ 层与第 $j + 1$ 层之间的连边为 $(P_j , P_{j+1})$ 与 $(Q_j , Q_{j+1})$，若：

则称它们在第 $j$ 层后产生了一个交点。两条路径的交点数为它们在第 $1, 2, \dots, k-1$ 层后产生的交点总数。对于整个路径方案，它的交点数为两两不同路径间交点数之和。例如下图是一个 $3$ 条路径，共 $3$ 个交点的例子，其中红色点是交点。

小 L 现在想知道有偶数个交点的路径方案数比有奇数个交点的路径方案数多多少个。两个路径方案被视为相同的，当且仅当它们的 $n_1$ 条路径按第一层起点编号顺序写下的 $k$ 元组能对应相同。由于最后的结果可能很大，请你输出它对 $998244353$（一个大质数）取模后的值。

输入格式

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

本题有多组数据，输入数据第一行一个正整数 $T$，表示数据组数。对于每组数据：

• 第一行一个正整数 $k$ ，表示一共有 $k$ 层顶点。
• 第二行包含 $k$ 个整数 $n_1, n_2,\dots, n_k$，依次表示每一层的顶点数量。保证 $n_1 = n_k$，且 $n_1\le n_i\le 2n_1$（$2\le i\le k − 1$）。
• 第三行包含 $k − 1$ 个整数 $m_1, m_2,\dots , m_{k−1}$，依次表示第 $j$（$1\le j < k$）层顶点到第 $j + 1$ 层顶点的边数。保证 $m_j\le n_j\times n_{j+1}$。
• 接下来有 $k − 1$ 段输入，第 $j$（$1\le j < k$）段输入包含 $m_j$ 行，每一行两个整数 $u, v$，表示第 $j$ 层的 $u$ 号顶点有一条边连向第 $j + 1$ 层的 $v$ 号顶点。

数据保证图中不会出现重边。

输出格式

输出到文件 xpath.out 中。 输出共 $T$ 行，每行一个整数，表示该组数据的答案对 $998244353$ 取模后的值。

1
3
2 3 2
4 4
1 1
1 2
2 1
2 3
1 2
2 1
3 1
3 2

1

样例解释 1

偶数个交点的方案有 $2$ 个，奇数个交点的方案有 $1$ 个，所以答案为 $1$。
将下表中路径 $1$ 和路径 $2$ 的方案交换，将会得到相同的方案，例如路径 $1$ 为 $(2, 3, 1)$ 且路径 $2$ 为 $(1, 1, 2)$ 的方案与方案 $1$ 是相同的方案，所以不会被计入答案。

样例 2

见选手目录下的 xpath2.in 与 xpath2.ans。

该样例约束与测试点 $7\sim 8$ 一致。

样例 3

见选手目录下的 xpath3.in 与 xpath3.ans。

该样例约束与测试点 $9\sim 10$ 一致。

样例 4

见选手目录下的 xpath4.in 与 xpath4.ans。

该样例约束与测试点 $14\sim 15$ 一致。

数据规模与约定

对于所有测试数据：$2\le k\le 100$，$2\le n_1\le 100$，$1\le T\le 5$。

每个测试点中，保证 $n_1 > 10$ 的数据只有 $1$ 组。

特殊性质 $\text{A}$：对于所有 $i$（$2\le i\le k − 1$）满足 $n_i = n_1$。
特殊性质 $\text{B}$：保证路径方案总数至多为 $1$。