Third Grader's Task

Tyler, a little boy, noticed magnets with symbols on the kitchen fridge. The magnets can be lined up to form a string $s$.

Tyler likes strings, especially ones that are lexicographically less than string $t$. After playing with the magnets, he wonders how many distinct strings can be made by rearranging the letters of $s$ so that the result is lexicographically less than $t$. Tyler is only in third grade and cannot answer this, so count the permutations of the letters of $s$ that are lexicographically less than $t$.

A string $x$ is lexicographically less than a string $y$ if one of the following conditions holds.

• There is a position $m$ present in both strings such that the strings are equal before the $m$-th symbol, and the $m$-th symbol of $x$ is less than the $m$-th symbol of $y$.
• $x$ is a prefix of $y$.

Because the answer can be 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$.

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

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

Print one integer: the number of rearrangements of the letters of $s$ that are lexicographically less than $t$, modulo $998\,244\,353$.

In the first sample, the counted strings are [1 2 2] and [2 1 2]. The string [2 2 1] is lexicographically greater than [2 1 2 1], so it is not counted.

In the second sample, every string except [4 3 2 1] is counted, so the answer is $4! - 1 = 23$.

In the third sample, only [1 1 1 2] is counted.