Dungeon Defense
Limits: 2 sec., 512 MiB
This statement was translated automatically from Ukrainian.
In the New York sewer, Splinter gave the Teenage Mutant Ninja Turtles the task of setting up a defensive wall.
The wall has the shape of a rectangle of height \(h\) and width \(w\). The wall is divided into \(w\) columns of unit width and \(h\) rows of unit height.
The turtles must build a defense line on this wall. A defense line is a polygonal chain that satisfies the following conditions.
The defense line starts at the bottom-left corner of the wall.
The defense line ends at the top-right corner of the wall.
The defense line consists of \(w + h\) segments of unit length, each of which goes right or up.
Donatello also put forward additional conditions for the defense line.
In the row numbered \(i\), the vertical segment is at a distance \(a_i\) from the left edge of the wall.
In the column numbered \(j\), the horizontal segment is at a distance \(b_j\) above the bottom edge of the wall.
The defense line in the example. The values of \(a_i\) on the left and \(b_j\) at the bottom.
Donatello thought everything through carefully, so there exists a defense line that satisfies his conditions.
Donatello instructed Michelangelo to write all \(h + w\) numbers in a notebook, but Michelangelo accidentally mixed up their order. Now a set of numbers \(d_i\) is recorded in the notebook, and it is unknown which of them correspond to what.
Fortunately, Michelangelo only mixed up the order of the numbers, but recorded the values themselves unchanged.
Help the turtles and find how many ways there are to build a defense line that could have been originally planned by the turtles. Since the answer can be very large, output the remainder of its division by the prime number \(998244353\).
Input
The first line gives two integers \(h\) and \(w\) — the height and width of the wall.
In the second line, \(h + w\) integers \(d_i\) are given, which Michelangelo wrote in the notebook in arbitrary order.
Output
Output an integer — the remainder of dividing the number of ways to build a defense line by the prime number \(998244353\).
Constraints
\(1 \le w, h \le 10^5\),
\(0 \le d_i \le \max(w, h)\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 5 0 1 1 1 3 2 4 4 4 | 4 |
Notes
The problem statement shows one of the 4 possible ways to build a defense line. Here are the other 3 ways:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|