CF935D Fafa and Ancient Alphabet

古埃及人以使用大量符号在神庙的墙壁上书写而闻名。Fafa 和 Fifa 来到其中一座神庙，发现墙上写着两个长度相等且非空的单词 $S_1$ 和 $S_2$，一个在另一个的下方。由于这座神庙非常古老，单词中的某些符号已经被抹去。对于任意被抹去的位置，符号集中的每个符号都有相等的概率出现在该位置。 Fifa 向 Fafa 发起挑战，让他计算 $S_1$ 字典序大于 $S_2$ 的概率。你能帮助 Fafa 完成这个任务吗？ 你知道古埃及字母表中有 $m$ 个不同的字符，在本题中这些字符用 $1$ 到 $m$ 的整数按字母顺序表示。对于长度相同的两个单词 $x$ 和 $y$，如果它们在某个位置之前都相同，而在该位置 $x$ 的字符大于 $y$ 的字符，则称 $x$ 的字典序大于 $y$。 可以证明，这个概率等于某个分数 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 互质，且 $Q$ 可被 $10^9+7$ 整除。请输出 $\frac{P}{Q} \bmod 10^9+7$，即小于 $10^9+7$ 的非负整数 $x$，使得 $x \equiv \frac{P}{Q} \pmod{10^9+7}$。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示两个单词的长度和字母表的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq m$），表示 $S_1$ 的符号。如果 $a_i=0$，则第 $i$ 位的符号已被抹去。 第三行以相同格式给出 $S_2$。

输出 $\frac{P}{Q} \bmod 10^9+7$，其中 $P$ 和 $Q$ 互质，$\frac{P}{Q}$ 是本题的答案。

在第一个样例中，第一个单词可以变为 $(1)$ 或 $(2)$。只有第二种情况会使其字典序大于第二个单词。因此答案为 $\frac{1}{2}$，即 $500000004$，因为 $500000004 \times 2 \equiv 1 \pmod{10^9+7}$。 在第二个样例中，无论第二个单词中的零如何替换，都无法使第一个单词字典序大于第二个单词。因此答案为 $0$。 由 ChatGPT 4.1 翻译