3학년의 과제

냉장고에서 기호가 적힌 자석을 발견한 어린 타일러가 있다. 이 자석들을 일렬로 늘어놓으면 문자열 $s$가 된다.

타일러는 문자열을 좋아하고, 특히 문자열 $t$보다 사전순으로 작은 문자열을 좋아한다. 자석을 가지고 놀던 타일러는 $s$의 글자를 재배열해 만들 수 있는 서로 다른 문자열 중 $t$보다 사전순으로 작은 것이 몇 개인지 궁금해한다. 타일러는 아직 3학년이라 이 질문에 답하지 못한다. $s$의 글자를 재배열한 결과 중 $t$보다 사전순으로 작은 것의 개수를 구하라.

문자열 $x$가 $y$보다 사전순으로 작다는 것은 다음 조건 중 하나를 만족한다는 뜻이다.

• 두 문자열에 모두 존재하는 위치 $m$이 있고, $m$번째 기호 이전까지 두 문자열이 같으며, $x$의 $m$번째 기호가 $y$의 $m$번째 기호보다 작다.
• $x$가 $y$의 접두사이다.

답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 200\,000$)이 주어진다. 각각 문자열 $s$와 $t$의 길이이다.

둘째 줄에 $s$의 기호 $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 200\,000$)이 주어진다.

셋째 줄에 $t$의 기호 $t_1, t_2, \ldots, t_m$ ($1 \le t_i \le 200\,000$)이 주어진다.

$s$의 글자를 재배열해 만들 수 있는 문자열 중 $t$보다 사전순으로 작은 것의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서 세는 문자열은 [1 2 2]와 [2 1 2]이다. [2 2 1]은 [2 1 2 1]보다 사전순으로 크므로 세지 않는다.

두 번째 예제에서는 [4 3 2 1]을 제외한 모든 문자열을 세므로 답은 $4! - 1 = 23$이다.

세 번째 예제에서는 [1 1 1 2]만 센다.