You are given two array S1 and S2 of equal length, where some elements are missing. All the elements of the array have equal probability of being missed.
You have to calculate the probability that S1 is lexicographically greater than S2.
The elements of the arrays are between 1 and m. 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 P/Q , where P and Q are coprime integers, and Q!=0 (mod 109+7 ) . Print as the answer the value R = P∗Q−1 (mod 109+7) , i. e. such a non-negative integer less than 109 + 7 , such that R*Q =P (mod 109+7) , where a=b (mod 109+7) means that a and b give the same remainders when divided by m.
Input Format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105) -- where n is the size of array and m is maximum value in array.
The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ m) — the symbols of S1. If ai = 0, then the symbol at position i was erased.
The third line contains n integers representing S2 with the same format as S1.
Output Format:
Print the value , where P and Q are coprime and is the answer to the problem.