codeforces#P1648C. Tyler and Strings

    ID: 32758 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>combinatoricsdata structuresexpression parsingimplementationstrings

Tyler and Strings

Description

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

Input

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

Output

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

Samples

3 4
1 2 2
2 1 2 1
2
4 4
1 2 3 4
4 3 2 1
23
4 3
1 1 1 2
1 1 2
1

Note

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.