codeforces#P1976E. Splittable Permutations
Splittable Permutations
Description
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:
- 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]$;
- 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]$;
- 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.
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]$.
Print one integer — the number of valid permutations, taken modulo $998244353$.
Input
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
Print one integer — the number of valid permutations, taken modulo $998244353$.
6 3
6 4 4
5 5 2
10 1
10
9
4 1
2
4
30
1814400
8