← 返回题目列表

Codeforces · 935/D

D. 法法与古字母

中文机器翻译题面 查看原题

众所周知,古埃及人使用一大组符号 $$\Sigma$$ 在寺庙的墙壁上书写。法法和菲法来到其中一座寺庙,发现寺庙的墙壁上写着两个等长的非空字“S1”和“S2”。由于这座寺庙非常古老,文字中的一些符号被抹掉了。集合 $$\Sigma$$ 中的符号处于任何已擦除符号位置的概率相同。

FIFA 要求 Fafa 计算 S1 按字典顺序大于 S2 的概率。你能帮助Fafa完成这个任务吗?

你知道 $$\sum = m$$, i。 e.埃及字母表中有 m 个不同的字符,在这个问题中,这些字符按字母顺序用 1 到 m 的整数表示。单词 x 按字典顺序大于相同长度的单词 y,如果单词在某个位置相同,则单词 x 比单词 y 具有更大的字符。

我们可以证明概率等于某个分数 $$P / Q$$,其中 P 和 Q 是互质整数,并且 $$Q \not\equiv 0 \pmod{10^9 + 7}$$。打印值 $$R = P \cdot Q^{-1} \mod (10^9 + 7)$$ 作为答案,i。 e.这样一个小于 109 + 7 的非负整数,使得 $$R \cdot Q \equiv P \mod (10^9 + 7)$$,其中 $$a \equiv b \mod (m)$$ 表示 a 和 b 除以 m 时得到相同的余数。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 分别是两个单词的长度和字母表 $$\Sigma$$ 的大小。

第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ m) — S1 的符号。如果ai = 0,则位置i处的符号被擦除。

第三行包含n个整数,代表S2,其格式与S1相同。

输出

打印值 $$P \cdot Q^{-1} \mod (10^9 + 7)$$,其中 P 和 Q 互质,$$P / Q$$ 是问题的答案。

示例

输入 #1

1 2
0
1

输出 #1

500000004

输入 #2

1 2
1
0

输出 #2

0

输入 #3

7 26
0 15 12 9 13 0 14
11 1 0 13 15 12 0

输出 #3

230769233

注意

在第一个样本中,第一个单词可以转换为(1)或(2)。第二个选项是唯一一个使其在字典顺序上大于第二个单词的选项。因此,问题的答案将是 $${ \frac { 1 } { 2 } } \mod ( 1 0 ^ { 9 } + 7 )$$,即 500000004,因为 $$(500000004 \cdot 2) \bmod (10^9 + 7) = 1$$。

在第二个示例中,没有替换第二个单词中的零,这将使第一个单词按字典顺序变大。所以,问题的答案是 $${ \frac { 0 } { 1 } } { \bmod { ( 1 0 ^ { 9 } + 7 ) } }$$,即 0。