30674번 - 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円$.

제한

서브태스크

노트

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