#P18636. Junk Problem

Junk Problem

Junk Problem

给定一个有 nn 行、mm 列的网格图,顶点用 (x,y)(x,y) 表示,第 xx 行、第 yy 列。

通常只能沿边向下或向右行走,即从 (x,y)(x,y) 走到 (x+1,y)(x+1,y) 或 (x,y+1)(x,y+1),前提是目标顶点仍在网格内。

另外有 kk 条水平边是双向边:如果 (x,y)(x,y) 与 (x,y+1)(x,y+1) 之间的边被指定为双向边,则也允许从 (x,y+1)(x,y+1) 走到 (x,y)(x,y)。保证任意两条双向边都没有公共端点。

你需要选出 ll 条顶点互不相交的简单路径,其中第 ii 条从 (1,ai)(1,a_i) 出发,到 (n,bi)(n,b_i) 结束。简单路径不能重复经过同一个顶点;任意两条路径也不能经过同一个顶点。

对于这样的一组路径,如果一条双向边的两个端点都没有被任何路径访问,就称它为坏边。

求不存在坏边的路径组数量,对 998244353998244353 取模。路径由各自经过的顶点序列区分,第 ii 条路径的起点和终点已经指定。

注意:一条双向边只要有至少一个端点被任意路径访问,就不是坏边;并不要求路径实际经过这条边,也不要求两个端点都被访问。

输入格式

第一行四个整数 n,m,l,kn,m,l,k。

第二行 ll 个整数 a1,a2,…,ala_1,a_2,\ldots,a_l,表示各条路径在第一行的起点列号。

第三行 ll 个整数 b1,b2,…,blb_1,b_2,\ldots,b_l,表示对应路径在第 nn 行的终点列号。

接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示 (xi,yi)(x_i,y_i) 与 (xi,yi+1)(x_i,y_i+1) 之间的边是双向边。

输出格式

输出一个整数,表示合法路径组数量对 998244353998244353 取模的结果。

数据范围

  • 2≤n,m≤1002\le n,m\le100;
  • 1≤l≤501\le l\le50,0≤k≤500\le k\le50;
  • 1≤a1<a2<⋯<al≤m1\le a_1<a_2<\cdots<a_l\le m;
  • 1≤b1<b2<⋯<bl≤m1\le b_1<b_2<\cdots<b_l\le m;
  • 1≤xi≤n1\le x_i\le n,1≤yi<m1\le y_i<m;
  • 任意两条双向边不共享端点。

输入只有一组数据。起终点的条件也隐含 l≤ml\le m。

样例输入 1

2 2 1 2
2
1
1 1
2 1

样例输出 1

2

样例输入 2

3 4 2 1
1 4
1 4
2 2

样例输出 2

0

样例输入 3

10 10 3 4
1 2 3
8 9 10
2 3
2 5
4 6
7 8

样例输出 3

388035318