在查看厨房冰箱时,小男孩泰勒注意到带有符号的磁铁,可以将其排列成字符串$$$s$$$。
Tyler 喜欢字符串,尤其是那些按字典顺序小于另一个字符串 $$$t$$$ 的字符串。在玩了冰箱上的磁铁后,他想知道,通过重新排列字符串 $$$s$$$ 中的字母,可以组成多少个不同的字符串,使得所得字符串按字典顺序小于字符串 $$$t$$$?泰勒太年轻,所以他无法回答这个问题。 Tyler 使用的字母表非常大,因此为了您的方便,他已经将 $$$s$$$ 和 $$$t$$$ 中的相同字母替换为相同的整数,并保持不同的字母已替换为不同的整数。
如果满足以下条件之一,我们称字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$:
- 两个字符串中都存在符号 $$$m$$$ 的位置,因此在第 $$$m$$$ 个符号之前,字符串相等,并且字符串 $$$x$$$ 的第 $$$m$$$ 个符号小于字符串 $$$y$$$ 的第 $$$m$$$ 个符号。
- 字符串 $$$x$$$ 是字符串 $$$y$$$ 和 $$$x \neq y$$$ 的前缀。
因为答案可能太大,所以打印它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 200\,000$$$)——分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$s_1, s_2, s_3, \ldots, s_n$$$ ($$$1 \le s_i \le 200\,000$$$) — 字符串 $$$s$$$ 的字母。
第三行包含 $$$m$$$ 整数 $$$t_1, t_2, t_3, \ldots, t_m$$$ ($$$1 \le t_i \le 200\,000$$$) — 字符串 $$$t$$$ 的字母。
输出
打印单个数字 - 按字典顺序小于 $$$t$$$ 的字符串数量,可以通过重新排列 $$$s$$$ 中的字母,模 $$$998\,244\,353$$$ 获得。
示例
输入 #1
3 4 1 2 2 2 1 2 1
输出 #1
2
输入 #2
4 4 1 2 3 4 4 3 2 1
输出 #2
23
输入 #3
4 3 1 1 1 2 1 1 2
输出 #3
1
注意
在第一个示例中,我们感兴趣的字符串是 $$$[1\, 2\, 2]$$$ 和 $$$[2\, 1\, 2]$$$。字符串 $$$[2\, 2\, 1]$$$ 按字典顺序比字符串 $$$[2\, 1\, 2\, 1]$$$ 大,所以我们不计算它。
在第二个示例中,除了 $$$[4\, 3\, 2\, 1]$$$ 之外的所有字符串都计算在内,因此答案是 $$$4! - 1 = 23$$$。
在第三个示例中,仅字符串 $$$[1\, 1\, 1\, 2]$$$ 有效。