Splittable Permutations
Contest: Educational Codeforces Round 166 (Rated for Div. 2)
Difficulty rating: 2500
Tags: combinatorics, data structures, dfs and similar, greedy, math, trees

Initially, we had one array, which was a permutation of size $$$n$$$ (an array of size $$$n$$$ where each integer from $$$1$$$ to $$$n$$$ appears exactly once).

We performed $$$q$$$ operations. During the $$$i$$$-th operation, we did the following:

- choose any array we have with at least $$$2$$$ elements;
- split it into two non-empty arrays (prefix and suffix);
- write two integers $$$l_i$$$ and $$$r_i$$$, where $$$l_i$$$ is the maximum element in the left part which we get after the split, and $$$r_i$$$ is the maximum element in the right part;
- remove the array we've chosen from the pool of arrays we can use, and add the two resulting parts into the pool.

For example, suppose the initial array was $$$[6, 3, 4, 1, 2, 5]$$$, and we performed the following operations:

1. choose the array $$$[6, 3, 4, 1, 2, 5]$$$ and split it into $$$[6, 3]$$$ and $$$[4, 1, 2, 5]$$$. Then we write $$$l_1 = 6$$$ and $$$r_1 = 5$$$, and the arrays we have are $$$[6, 3]$$$ and $$$[4, 1, 2, 5]$$$;
2. choose the array $$$[4, 1, 2, 5]$$$ and split it into $$$[4, 1, 2]$$$ and $$$[5]$$$. Then we write $$$l_2 = 4$$$ and $$$r_2 = 5$$$, and the arrays we have are $$$[6, 3]$$$, $$$[4, 1, 2]$$$ and $$$[5]$$$;
3. choose the array $$$[4, 1, 2]$$$ and split it into $$$[4]$$$ and $$$[1, 2]$$$. Then we write $$$l_3 = 4$$$ and $$$r_3 = 2$$$, and the arrays we have are $$$[6, 3]$$$, $$$[4]$$$, $$$[1, 2]$$$ and $$$[5]$$$.

You are given two integers $$$n$$$ and $$$q$$$, and two sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$. A permutation of size $$$n$$$ is called valid if we can perform $$$q$$$ operations and produce the given sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$.

Calculate the number of valid permutations.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le q < n \le 3 \cdot 10^5$$$).

The second line contains $$$q$$$ integers $$$l_1, l_2, \dots, l_q$$$ ($$$1 \le l_i \le n$$$).

The third line contains $$$q$$$ integers $$$r_1, r_2, \dots, r_q$$$ ($$$1 \le r_i \le n$$$).

Additional constraint on the input: there exists at least one permutation which can produce the given sequences $$$[l_1, l_2, \dots, l_q]$$$ and $$$[r_1, r_2, \dots, r_q]$$$.

Output format:
Print one integer — the number of valid permutations, taken modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
6 3
6 4 4
5 5 2

Example output:
30

Example input:
10 1
10
9

Example output:
1814400

Editorial:
First, let's deal with the case $$$q=n-1$$$. In this case, after all operations are performed, all arrays have only one element each, and can no longer be split. We can show that the initial order of elements can be restored uniquely in this case. For example, we can start with $$$n$$$ arrays consisting of single elements (one array for each integer from $$$1$$$ to $$$n$$$), and "undo" the operations to restore the initial order. "Undoing" the operations means linking two arrays together, and we don't have any choice which arrays and in which order we link, so the result of each operation is uniquely determined. So, in the case $$$q = n-1$$$, the answer is $$$1$$$.
What about the case $$$q < n-1$$$? Let's divide all integers from $$$1$$$ to $$$n$$$ into two groups: the integers from the sequences $$$l$$$ and/or $$$r$$$, and all other integers. We can use the same process to show that the order of elements from the first group (the ones which were present in at least one of the given sequences) is unique, and we can restore their order using something like DSU (performing operations from the last to the first) or a double-linked list (performing operations from the first to the last).
So, suppose we restored the order of elements which are present in the input; we need to insert all of the remaining integers and don't make the sequence of operations invalid. We have an array of $$$q+1$$$ elements, the order of which is fixed; and there are $$$q+2$$$ "buckets" where we can insert the remaining elements (before the first element, between the first and the second, and so on).
For each of these "buckets", let's consider the maximum between the elements on the borders of the bucket (the fixed elements between which we insert the remaining elements). It's quite easy to see that each element we insert in a "bucket" should be less than this maximum: suppose the fixed element on the left border is $$$y$$$, the fixed element on the right border is $$$z$$$, and there was an element $$$x > \max(y,z)$$$ between them. After we performed all operations, $$$x$$$ is either in the same array as $$$y$$$ or in the same array as $$$z$$$; so when we "made" that array during an operation, we would have written the integer $$$x$$$ (or some even greater integer) instead of $$$y$$$ or $$$z$$$.
And we can also show the opposite: if each element in each "bucket" is less than the maximum of the two elements bordering the bucket, the operation sequence is valid. To prove it, let's merge every bucket with the greater of the elements on its borders, and then again "undo" all operations to restore the original order of elements.
So, for each remaining element, there are some buckets where we can put it, and some buckets where we can't. However, we also have to consider the relative order of the elements we insert in the same bucket.
Let's start with the sequence of "fixed" elements, and insert the remaining elements one by one from the greatest integer to the smallest integer. We can show that every time we insert an element in this order, the number of places where it can go does not depend on where we inserted the previous elements. Suppose we insert an element which "fits" into $$$b$$$ buckets, and before inserting it, we also inserted $$$k$$$ other elements. Then there are exactly $$$b+k$$$ places where this element can fit, because every element we inserted earlier went into one of those same $$$b$$$ buckets and split that bucket into two. So, maintaining these two numbers (the number of available buckets and the number of elements we already inserted) is enough, and the positions of elements we inserted does not matter.
This allows us to count the number of possible permutations in $$$O(n)$$$.