You are given a grid graph with $$$n$$$ rows and $$$m$$$ columns. Most edges are directed, which means you can walk from $$$(x, y)$$$ to $$$(x + 1, y)$$$ or $$$(x, y + 1)$$$. $$$k$$$ horizontal edges are bidirectional, which means you can walk from $$$(x, y)$$$ to $$$(x, y + 1)$$$, and $$$(x, y + 1)$$$ to $$$(x, y)$$$ too. It's guaranteed that there is no pair of bidirectional edges that share an endpoint.
You need to find $$$l$$$ vertex-disjoint simple paths, where the $$$i$$$-th is from $$$(1, a_i)$$$ to $$$(n, b_i)$$$. For a set of paths, we call a bidirectional edge bad if neither of its endpoints is visited by any of the paths in this set.
Output the number of all $$$l$$$ vertex-disjoint simple paths without any bad edges, modulo $$$998244353$$$.
In the first line, $$$n, m, l, k$$$ ($$$2\leq n, m\leq 100, 1\leq l\leq 50, 0\leq k\leq 50$$$).
In the second line, $$$a_1, a_2, \dots, a_l$$$ ($$$1\leq a_1 \lt a_2 \lt \dots \lt a_l \leq m$$$).
In the third line, $$$b_1, b_2, \dots, b_l$$$ ($$$1\leq b_1 \lt b_2 \lt \dots \lt b_l \leq m$$$).
In the following $$$k$$$ lines, $$$x_i, y_i$$$ ($$$1\leq x_i \leq n, 1 \leq y_i \lt m$$$) each line, which denote that the edge $$$(x_i, y_i)$$$ to $$$(x_i, y_i + 1)$$$ is bidirectional.
It's guaranteed that there is no pair of bidirectional edges that share an endpoint.
One integer — the answer.
2 2 1 2 2 1 1 1 2 1
2
3 4 2 1 1 4 1 4 2 2
0
10 10 3 4 1 2 3 8 9 10 2 3 2 5 4 6 7 8
388035318
