human
Write me a Python program to print as the answer the value $R = P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, i given the following:
Solve in Python:
Ancient Egyptians are known to have used a large set of symbols $\sum$ 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 $\sum$ 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 $|\sum|= m$, 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 $P / Q$, where P and Q are coprime integers, and $Q \neq 0 \text{mod}(10^{9} + 7)$. Print as the answer the value $R = P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, i. e. such a non-negative integer less than 10^9 + 7, such that $R \cdot Q \equiv P \operatorname{mod}(10^{9} + 7)$, where $a \equiv b \text{mod}(m)$ 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 ≤ 10^5) — the length of each of the two words and the size of the alphabet $\sum$, 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 $P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, where P and Q are coprime and $P / Q$ is the answer to the problem.

-----Examples-----
Input
1 2
0
1

Output
500000004

Input
1 2
1
0

Output
0

Input
7 26
0 15 12 9 13 0 14
11 1 0 13 15...
assistant
#Here is Python program to print as the answer the value $R = P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$, i.

import sys

MOD = 1000000007

def solve(io):
  N = io.readInt()
  M = io.readInt()
  S = io.readIntArray(N)
  T = io.readIntArray(N)
  
  P = 0
  Q = 1
  A = 1
  B = 1
  for i in range(0, N):
    if S[i] == 0 or T[i] == 0:
      if S[i] == 0 and T[i] == 0:
        gtTop = M * (M - 1) * A
        gtBot = 2 * M * M * B
        eqTop = 1
        eqBot = M
      elif S[i] == 0:
        gtTop = (M - T[i]) * A
        gtBot = M * B
        eqTop = 1
        eqBot = M
      elif T[i] == 0:
        gtTop = (S[i] - 1) * A
        gtBot = M * B
        eqTop = 1
        eqBot = M
    elif S[i] > T[i]:
      gtTop = A
      gtBot = B
      eqTop = 0
      eqBot = 1
    elif S[i] < T[i]:
      gtTop = 0
      gtBot = 1
      eqTop = 0
      eqBot = 1
    elif S[i] == T[i]:
      gtTop = 0
      gtBot = 1
      eqTop = 1
      eqBot = 1
    P, Q = P * gtBot + gtTop * Q, Q * gtBot
    P %= MOD
    Q %= MOD
    A = (A * eqTop) % MOD
    B = (B * eqBot) % MOD
    if S[i] != 0 and T[i] != 0 and S[i] != T[i]:
      break
  io.println((P * modinv(Q, MOD)) % MOD)

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
 
def modinv(a, m):
	g, x, _ = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

# +---------------------+
# | TEMPLATE CODE BELOW |
# |    DO NOT MODIFY    |
# +---------------------+

# TODO: maybe reading byte-by-byte is faster than reading and parsing tokens.
class IO:
  input = None
  output = None
  raw = ""
  buf = []
  pos = 0
  
  def __init__(self, inputStream, outputStream):
    self.input = inputStream
    self.output = outputStream
  
  def readToBuffer(self):
    self.raw = self.input.readline().rstrip('\n')
    self.buf = self.raw.split()
    self.pos = 0
...