E. Splittable Permutations
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: 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\).