A14924. Tyler and Strings

While looking at the kitchen fridge, the little boy Tyler noticed magnets with symbols, that can be aligned into a string $s$ .

Tyler likes strings, and especially those that are lexicographically smaller than another 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 resulting string is lexicographically smaller than the string $t$ ? Tyler is too young, so he can't answer this question. The alphabet Tyler uses is very large, so for your convenience he has already replaced the same letters in $s$ and $t$ to the same integers, keeping that different letters have been replaced to different integers.

We call a string $x$ lexicographically smaller than a 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 $x$ is smaller than $m$ -th symbol of string $y$ .
- String $x$ is the prefix of string $y$ and $x \neq 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$ ) — the lengths of strings $s$ and $t$ respectively.

The second line contains $n$ integers $s_1, s_2, s_3, \ldots, s_n$ ( $1 \le s_i \le 200\,000$ ) — letters of the string $s$ .

The third line contains $m$ integers $t_1, t_2, t_3, \ldots, t_m$ ( $1 \le t_i \le 200\,000$ ) — letters of the string $t$ .

Print a single number — the number of strings lexicographically smaller than $t$ that can be obtained by rearranging the letters in $s$ , modulo $998\,244\,353$ .

In the first example, the strings we are interested in are $[1\, 2\, 2]$ and $[2\, 1\, 2]$ . The string $[2\, 2\, 1]$ is lexicographically larger than the string $[2\, 1\, 2\, 1]$ , so we don't count it.

In the second example, all strings count except $[4\, 3\, 2\, 1]$ , so the answer is $4! - 1 = 23$ .

In the third example, only the string $[1\, 1\, 1\, 2]$ counts.