题目描述

题目译自 Open Olympiad in Informatics 2022 Day2 T3 「Задача для третьеклассника / Third grader’s task」。

小泰勒走进厨房，看到冰箱上用磁铁拼出了一串字符串 $s$。他立刻发现了其中的无限潜力！

泰勒喜欢字符串，尤其是那些在字典序上小于字符串 $t$ 的字符串。在玩冰箱上的磁铁时，他开始思考，通过重新排列字符串 $s$ 中的字母，他能拼出多少个不同的、字典序小于 $t$ 的字符串。由于他只在二年级，无法自己计算这个数量，所以他请求你的帮助！

注意，字符串 $x$ 在字典序上小于字符串 $y$，如果满足以下两个条件之一：

• 存在某个位置 $m$，在该位置之前两字符串相同，而在位置 $m$ 上，字符串 $x$ 的字符小于字符串 $y$ 的字符；
• 字符串 $x$ 是字符串 $y$ 的严格前缀（即通过去掉 $y$ 末尾的一个或多个字符得到）。

由于答案可能非常大，请将结果对 $998244353$ 取模后输出。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 200000)$，分别表示字符串 $s$ 和 $t$ 的长度。

第二行包含 $n$ 个整数 $s_1, s_2, s_3, \ldots, s_n$ $(1 \leq s_i \leq 200000)$，表示字符串 $s$ 的字母。

第三行包含 $m$ 个整数 $t_1, t_2, t_3, \ldots, t_m$ $(1 \leq t_i \leq 200000)$，表示字符串 $t$ 的字母。

输出格式

输出一个整数，即通过重新排列 $s$ 中的字母可以得到的、字典序小于 $t$ 的不同字符串的数量，对 $998244353$ 取模。

3 4
1 2 2
2 1 2 1

2

在第一个样例中，符合条件的字符串有 $[1\ 2\ 2]$ 和 $[2\ 1\ 2]$。字符串 $[2\ 2\ 1]$ 在字典序上大于 $[2\ 1\ 2\ 1]$，因此不计入。

4 4
1 2 3 4
4 3 2 1

23

在第二个样例中，除了 $[4\ 3\ 2\ 1]$ 之外的所有字符串都符合条件，因此有 $4! - 1 = 23$ 个。

4 3
1 1 1 2
1 1 2

1

在第三个样例中，只有字符串 $[1\ 1\ 1\ 2]$ 符合条件。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。