407680: GYM102870 J Junction of Orz Pandas

The Orz Pandas are building a electric power grid. There are $$$n$$$ vertical power lines and $$$m$$$ horizontal power lines. To make the power grid stable, the Orz Pandas should build one junction between each vertical power line and each horizontal power line. There should be $$$n\times m$$$ junctions.

Each junction has a design parameter. Let's use $$$p_{ij}$$$ to denote the design parameter of the junction between the $$$i$$$-th vertical power line and the $$$j$$$-th horizontal power line. To ensure the safety of the power grid, it must satisfies the following conditions:

• $$$p_{ij}$$$ is a positive integer
• $$$a_i=\max\limits_{1\le j\le m} \{p_{ij}\} $$$, for each $$$i$$$
• $$$b_j=\,\max\limits_{1\le i\le n} \{p_{ij}\} $$$, for each $$$j$$$

Now the Orz Panda engineers have already calculated $$$a_i$$$ and $$$b_j$$$ for each power line. It's very easy to output a possible solution of $$$p_{ij}$$$ satisifying those conditions, or report they can't be satisified. To make the problem more challenging, the Orz Pandas want you to output the number of different solutions satisifying those conditions.

Two solutions $$$p$$$ and $$$q$$$ are considered different if and only if there exists a pair $$$(i, j)$$$, such that $$$p_{ij} \neq q_{ij}$$$. Since the answer may be very large, you should output it modulo $$$998244353$$$.

There is only one test case in the input file.

The first line contains two integers $$$n$$$ and $$$m$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \cdots, b_n$$$.

It's guaranteed that $$$1 \leq n, m \leq 10^5$$$, and $$$1 \leq a_i , b_i \leq 10^9$$$.

Output one line containing the number of different answers, modulo $$$998244353$$$.

3 3
1 2 3
1 2 3

5

For the sample, the possible solutions are:

$$$$$$ \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 2 & 1 \\ \hline 1 & 1 & 3 \\ \hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 2 & 2 \\ \hline 1 & 1 & 3 \\ \hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 2 & 1 \\ \hline 1 & 2 & 3 \\ \hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 2 & 2 \\ \hline 1 & 2 & 3 \\ \hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 1 & 2 \\ \hline 1 & 2 & 3 \\ \hline \end{array} $$$$$$