English · Original
Chinese · Translation
Formal · Original
Ancient Egyptians are known to have used a large set of symbols to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words _S_1 and _S_2 of equal lengths on the wall of temple written one below the other. Since this temple is very ancient, some symbols from the words were erased. The symbols in the set have equal probability for being in the position of any erased symbol.
Fifa challenged Fafa to calculate the probability that _S_1 is lexicographically greater than _S_2. Can you help Fafa with this task?
You know that , i. e. there were _m_ distinct characters in Egyptians' alphabet, in this problem these characters are denoted by integers from 1 to _m_ in alphabet order. A word _x_ is lexicographically greater than a word _y_ of the same length, if the words are same up to some position, and then the word _x_ has a larger character, than the word _y_.
We can prove that the probability equals to some fraction , where _P_ and _Q_ are coprime integers, and . Print as the answer the value , i. e. such a non-negative integer less than 109 + 7, such that , where means that _a_ and _b_ give the same remainders when divided by _m_.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105) — the length of each of the two words and the size of the alphabet , respectively.
The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ _m_) — the symbols of _S_1. If _a__i_ = 0, then the symbol at position _i_ was erased.
The third line contains _n_ integers representing _S_2 with the same format as _S_1.
## Output
Print the value , where _P_ and _Q_ are coprime and is the answer to the problem.
[samples]
## Note
In the first sample, the first word can be converted into (1) or (2). The second option is the only one that will make it lexicographically larger than the second word. So, the answer to the problem will be , that is 500000004, because .
In the second example, there is no replacement for the zero in the second word that will make the first one lexicographically larger. So, the answer to the problem is , that is 0.
古埃及人使用一组符号在神庙的墙壁上书写。Fafa 和 Fifa 前往其中一座神庙，发现墙上写有两个等长的非空单词 #cf_span[S1] 和 #cf_span[S2]，一个在另一个下方。由于这座神庙非常古老，一些符号已被擦除。集合 中的符号在任何被擦除位置出现的概率相等。
Fifa 挑战 Fafa 计算 #cf_span[S1] 字典序大于 #cf_span[S2] 的概率。你能帮助 Fafa 完成这个任务吗？
已知 ，即埃及字母表中有 #cf_span[m] 个不同的字符，本题中这些字符用从 #cf_span[1] 到 #cf_span[m] 的整数按字母顺序表示。一个单词 #cf_span[x] 字典序大于同长度的单词 #cf_span[y]，当且仅当这两个单词在某个位置之前完全相同，而在该位置之后，#cf_span[x] 的字符大于 #cf_span[y] 的字符。
我们可以证明，该概率等于某个分数 ，其中 #cf_span[P] 和 #cf_span[Q] 为互质整数，且 。请输出 ，即一个非负整数，小于 #cf_span[10^9 + 7]，满足 ，其中 表示 #cf_span[a] 和 #cf_span[b] 除以 #cf_span[m] 时余数相同。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 10^5]) —— 每个单词的长度和字母表大小。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ m]) —— #cf_span[S1] 的符号。若 #cf_span[ai = 0]，则位置 #cf_span[i] 的符号被擦除。
第三行包含 #cf_span[n] 个整数，表示 #cf_span[S2]，格式与 #cf_span[S1] 相同。
请输出 ，其中 #cf_span[P] 和 #cf_span[Q] 互质，且 为问题的答案。
在第一个样例中，第一个单词可以变为 (#cf_span[1]) 或 (#cf_span[2])。只有第二种情况会使它字典序大于第二个单词。因此，问题的答案为 ，即 #cf_span[500000004]，因为 。
在第二个样例中，不存在任何替换第二个单词中零的方法，能使第一个单词字典序更大。因此，问题的答案为 ，即 #cf_span[0]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 10^5]) —— 每个单词的长度和字母表大小。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ m]) —— #cf_span[S1] 的符号。若 #cf_span[ai = 0]，则位置 #cf_span[i] 的符号被擦除。
第三行包含 #cf_span[n] 个整数，表示 #cf_span[S2]，格式与 #cf_span[S1] 相同。
## Output
请输出 ，其中 #cf_span[P] 和 #cf_span[Q] 互质，且 为问题的答案。
[samples]
## Note
在第一个样例中，第一个单词可以变为 (#cf_span[1]) 或 (#cf_span[2])。只有第二种情况会使它字典序大于第二个单词。因此，问题的答案为 ，即 #cf_span[500000004]，因为 。
在第二个样例中，不存在任何替换第二个单词中零的方法，能使第一个单词字典序更大。因此，问题的答案为 ，即 #cf_span[0]。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $, with $ 1 \leq n, m \leq 10^5 $.
Let $ A = (a_1, \dots, a_n) $, $ B = (b_1, \dots, b_n) $ be two sequences of length $ n $, where each $ a_i, b_i \in \{0\} \cup \{1, 2, \dots, m\} $.
A value $ 0 $ denotes an erased symbol; non-zero values denote fixed symbols from the alphabet $ \{1, 2, \dots, m\} $.
Let $ \Omega $ be the set of all possible completions of $ A $ and $ B $ by replacing each $ 0 $ with a symbol in $ \{1, \dots, m\} $, uniformly and independently.
Let $ A', B' $ be random variables representing the completed words.
**Constraints**
- For each $ i \in \{1, \dots, n\} $:
- If $ a_i \neq 0 $, then $ A'_i = a_i $; else $ A'_i \sim \text{Uniform}(\{1, \dots, m\}) $.
- If $ b_i \neq 0 $, then $ B'_i = b_i $; else $ B'_i \sim \text{Uniform}(\{1, \dots, m\}) $.
- All replacements are independent.
**Objective**
Compute the probability $ \mathbb{P}(A' \succ B') $, where $ A' \succ B' $ means $ A' $ is lexicographically greater than $ B' $.
Let $ \mathbb{P}(A' \succ B') = \frac{P}{Q} $ in lowest terms.
Output $ P \cdot Q^{-1} \mod (10^9 + 7) $.
API Response (JSON)
{
"problem": {
"name": "D. Fafa and Ancient Alphabet",
"description": {
"content": "Ancient Egyptians are known to have used a large set of symbols to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words _S_1 and _S_2 of equal leng",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF935D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Ancient Egyptians are known to have used a large set of symbols to write on the walls of the temples. Fafa and Fifa went to one of the temples and found two non-empty words _S_1 and _S_2 of equal leng...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "古埃及人使用一组符号在神庙的墙壁上书写。Fafa 和 Fifa 前往其中一座神庙，发现墙上写有两个等长的非空单词 #cf_span[S1] 和 #cf_span[S2]，一个在另一个下方。由于这座神庙非常古老，一些符号已被擦除。集合 中的符号在任何被擦除位置出现的概率相等。\n\nFifa 挑战 Fafa 计算 #cf_span[S1] 字典序大于 #cf_span[S2] 的概率。你能帮助 Fafa...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n, m \\leq 10^5 $. \nLet $ A = (a_1, \\dots, a_n) $, $ B = (b_1, \\dots, b_n) $ be two sequences of length $ n $, where each $ a_i, b_i \\in ...",
"is_translate": false,
"language": "Formal"
}
]
}