P13547 [OOI 2022] Third grader's task

While looking at the kitchen fridge, little boy Tyler noticed magnets with symbols, that can be aligned into a string $s$. Tyler likes strings, and especially those that are lexicographically less than string $t$. After playing with magnets on the fridge he is wondering, how many distinct strings can be composed out of letters of string $s$ by rearranging them, so that the the resulting string is lexicographically less than string $t$. Tyler is studying only in the third grade, so he can not answer this question. Help him to calculate the number of permutations of letters of string $s$, that are lexicographically less than string $t$. We call string $x$ lexicographically less than string $y$ if one of the followings conditions is fulfilled: - There exists such position of symbol $m$ that is presented in both strings, so that before $m$-th symbol the strings are equal, and the $m$-th symbol of string $s$ is less than $m$-th symbol of string $y$. - String $x$ is the prefix of string $y$. Because the answer can be too large, print it modulo $998\,244\,353$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 200\,000$) --- lengths of strings $s$ and $t$. The second line contains $n$ integers $s_1, s_2, s_3 \ldots s_n$ ($1 \le s_i \le 200\,000$) --- symbols of string $s$. The third line contains $m$ integers $t_1, t_2, t_3 \ldots t_m$ ($1 \le t_i \le 200\,000$) --- symbols of string $t$.

Print the single integer --- the number of strings that are lexicographically less than $t$, that can be composed by rearranging letters of string $s$ modulo $998\,244\,353$.

### Note In the first sample, we should count strings $[1\ 2\ 2]$ and $[2\ 1\ 2]$. String $[2\ 2\ 1]$ is lexicographically grater than string $[2\ 1\ 2 1]$, so we do not count it. In the second sample we should count all strings except $[4\ 3\ 2\ 1]$, so the answer is $4! - 1 = 23$. In the third sample we should count only string $[1\ 1\ 1\ 2]$. ### Scoring The testset for this problem consists of 6 test groups. You get points for a group only if your solution passes all tests from this group and from all the required groups. $\textbf{Offline-evaluation}$ means that you will not get immediate feedback for this group and you will be able to see the outcome only after the end of the competition. Please note that it is not required to pass all sample test cases. | Group | Points | Additional constraints | < | Required groups | Comment | |:-----:|:------:|:---------------------:|:-:|:---------------:|:-------:| | | | $n, m$ | $s_i, t_i$ | | | | 0 | 0 | -- | -- | -- | Sample tests. | | 1 | 16 | $n, m \le 10$ | $s_i, t_i \le 10$ | 0 | | | 2 | 15 | -- | $s_i, t_i \le 2$ | -- | | | 3 | 11 | -- | $s_i, t_i \le 20$ | 0 -- 2 | | | 4 | 13 | -- | $s_i, t_i \le 200$ | 0 -- 3 | | | 5 | 12 | -- | -- | -- | In each of the strings individually all symbols are distinct | | 6 | 33 | -- | -- | 0 -- 5 | **Offline-evaluation.** |