CF1648C.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$.

当小男生泰勒看着厨房冰箱时，注意到上面贴着一些印有符号的磁贴，这些磁贴可以排列成一个字符串 $s$。

泰勒很喜欢字符串，尤其喜欢那些字典序小于另一个给定字符串 $t$ 的字符串。在冰箱上摆弄这些磁贴后，他开始思考：将字符串 $s$ 中的字符重新排列（即重排其字母），一共能组成多少个互不相同的字符串，使得得到的字符串字典序严格小于字符串 $t$？泰勒年纪太小，还无法回答这个问题。泰勒所用的字母表非常大，因此为方便起见，他已将 $s$ 和 $t$ 中相同的字母分别替换为相同的整数，且不同字母被替换为不同的整数。

我们称字符串 $x$ 字典序小于字符串 $y$，当且仅当满足以下任一条件：

• 存在某个位置 $m$（该位置在两个字符串中均有效），使得 $x$ 与 $y$ 在第 $m$ 位之前的所有字符完全相同，且 $x$ 的第 $m$ 个字符严格小于 $y$ 的第 $m$ 个字符；
• 字符串 $x$ 是字符串 $y$ 的真前缀（即 $x$ 是 $y$ 的前缀且 $x \neq y$）。

由于答案可能非常大，请将结果对 $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$.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 200\,000$），分别表示字符串 $s$ 和 $t$ 的长度。

第二行包含 $n$ 个整数 $s_1, s_2, s_3, \ldots, s_n$（$1 \le s_i \le 200\,000$），表示字符串 $s$ 的各个字符。

第三行包含 $m$ 个整数 $t_1, t_2, t_3, \ldots, t_m$（$1 \le t_i \le 200\,000$），表示字符串 $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$.

输出一个整数——即通过重新排列字符串 $s$ 中的字母所能得到的、字典序小于 $t$ 的字符串的个数，对 $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.

在第一个例子中，我们关注的字符串是 $[1\, 2\, 2]$ 和 $[2\, 1\, 2]$。字符串 $[2\, 2\, 1]$ 在字典序上大于字符串 $[2\, 1\, 2\, 1]$，因此不计入。

在第二个例子中，除 $[4\, 3\, 2\, 1]$ 外，所有字符串均计入，因此答案为 $4! - 1 = 23$。

在第三个例子中，仅有字符串 $[1\, 1\, 1\, 2]$ 计入。