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 12 0

Output
230769233



-----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 $\frac{1}{2} \operatorname{mod}(10^{9} + 7)$, that is 500000004, because $(500000004 \cdot 2) \operatorname{mod}(10^{9} + 7) = 1$.

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 $\frac{0}{1} \operatorname{mod}(10^{9} + 7)$, that is 0.

Difficulty: HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7

def invmod(x, mod):
	return pow(x, mod - 2, mod)
(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	if a[i] == 0 and b[i] == 0:
		(sp, sq) = (m * m, m)
		(tp, tq) = (m * m, m * (m - 1) // 2)
	elif a[i] == 0:
		(sp, sq) = (m, 1)
		(tp, tq) = (m, m - b[i])
	elif b[i] == 0:
		(sp, sq) = (m, 1)
		(tp, tq) = (m, a[i] - 1)
	else:
		(sp, sq) = (1, 1 if a[i] == b[i] else 0)
		(tp, tq) = (1, 1 if a[i] > b[i] else 0)
	dp[i] = sq * invmod(sp, mod) * dp[i + 1]
	dp[i] += tq * invmod(tp, mod)
	dp[i] %= mod
ans = dp[0]
print(ans)


from math import gcd
p = 10 ** 9 + 7

class RN:
	p = 10 ** 9 + 7

	def __init__(self, u, d):
		self.u = u
		self.d = d

	def __str__(self):
		return str(self.u) + '/' + str(self.d)

	def cleanup(self):
		self.u = self.u % p
		self.d = self.d % p

	def add(self, u, d):
		self.u = self.u * d + u * self.d
		self.d = self.d * d
		self.cleanup()

	def mult(self, u, d):
		return (self.u * u % p, self.d * d % p)

	def mult_ip(self, u, d):
		(self.u, self.d) = (self.u * u, self.d * d % p)

	def get_m_exp(self):
		self.cleanup()
		a = gcd(self.u, self.d)
		self.u //= a
		self.d //= a
		return pow(self.d, p - 2, p) * self.u % p
(n, m) = tuple(map(int, input().split()))
s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))

def sum_ch(n):
	return (n + 1) * n // 2

def sol(s1, s2, m):
	strgr = RN(0, 1)
	eq = RN(1, 1)
	for (gr, sm, i) in zip(s1, s2, range(len(s1))):
		strgr.cleanup()
		if gr != 0 and sm != 0:
			if gr == sm:
				continue
			elif gr < sm:
				return strgr.get_m_exp()
			else:
				strgr.add(eq.u, eq.d)
				return strgr.get_m_exp()
		else:
			if gr == sm == 0:
				strgr.add(*eq.mult(sum_ch(m - 1), m * m))
			elif gr == 0:
				strgr.add(*eq.mult(m - sm, m))
			else:
				strgr.add(*eq.mult(gr - 1, m))
			eq.mult_ip(1, m)
	return strgr.get_m_exp()
print(sol(s1, s2, m))


rd = lambda : list(map(int, input().split()))
M = 1000000007
inv = lambda x: (M - M // x) * inv(M % x) % M if x - 1 else 1
(n, m) = rd()
a = list(rd())
b = list(rd())
(p, q, r) = (0, 1, 1)
for i in range(n):
	(x, y) = (a[i], b[i])
	if x == 0 and y == 0:
		p = (p * m * m + r * ((m - 1) * m >> 1)) % M
		q = q * m * m % M
		r = r * m % M
	elif x == 0:
		p = (p * m + r * (m - y)) % M
		q = q * m % M
	elif y == 0:
		p = (p * m + r * (x - 1)) % M
		q = q * m % M
	elif x != y:
		if x > y:
			p = (p + r) % M
		break
print(p * inv(q) % M)


p = 10 ** 9 + 7
(n, m) = input().split()
n = int(n)
m = int(m)
a = input().split()
b = input().split()
a = [int(k) for k in a]
b = [int(k) for k in b]
invm = pow(m, p - 2, p)
inv2 = pow(2, p - 2, p)
ans = 0
for i in reversed(range(n)):
	if a[i] == 0 and b[i] == 0:
		ans = (inv2 * invm % p * (m - 1) + invm * ans) % p
	if a[i] == 0 and b[i] != 0:
		ans = ((m - b[i]) * invm + invm * ans) % p
	if a[i] != 0 and b[i] == 0:
		ans = ((a[i] - 1) * invm + invm * ans) % p
	if a[i] != 0 and b[i] != 0:
		if a[i] > b[i]:
			ans = 1
		elif b[i] > a[i]:
			ans = 0
		else:
			ans = ans
print(ans)


(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
mult = 1
mod = 10 ** 9 + 7
res = 0
m_inv = pow(m, mod - 2, mod)
for (x, y) in zip(a, b):
	if x and y:
		if x > y:
			res += mult
			res %= mod
			break
		elif x == y:
			continue
		else:
			break
	elif x:
		res += mult * (x - 1) * m_inv % mod
		res %= mod
		mult = mult * m_inv % mod
	elif y:
		res += mult * (m - y) * m_inv % mod
		res %= mod
		mult = mult * m_inv % mod
	else:
		res += mult * m * (m - 1) // 2 * m_inv * m_inv % mod
		res %= mod
		mult = mult * m_inv % mod
print(res)


(n, m) = map(int, input().split())
s1 = map(int, input().split())
s2 = map(int, input().split())
MOD = 10 ** 9 + 7
invm = pow(m, MOD - 2, MOD)
inv2 = pow(2, MOD - 2, MOD)
z = 0
p = 1
for (a, b) in zip(s1, s2):
	if a == 0 and b == 0:
		z = (z + p * ((m - 1) * (invm * inv2))) % MOD
		p = p * invm % MOD
	elif a == 0:
		z = (z + p * (m - b) * invm) % MOD
		p = p * invm % MOD
	elif b == 0:
		z = (z + p * (a - 1) * invm) % MOD
		p = p * invm % MOD
	elif a > b:
		z = (z + p) % MOD
		break
	elif a < b:
		break
print(z)


rd = lambda : map(int, input().split())
M = 1000000007
inv = lambda x: (M - M // x) * inv(M % x) % M if x - 1 else 1
(n, m) = rd()
a = list(rd())
b = list(rd())
i = 0
(p, q, r) = (0, 1, 1)
while i < n:
	(x, y) = (a[i], b[i])
	if x == 0 and y == 0:
		p = (p * m * m + r * ((m - 1) * m >> 1)) % M
		q = q * m * m % M
		r = r * m % M
	elif x == 0:
		p = (p * m + r * (m - y)) % M
		q = q * m % M
	elif y == 0:
		p = (p * m + r * (x - 1)) % M
		q = q * m % M
	elif x == y:
		pass
	else:
		if x > y:
			p = (p + r) % M
		break
	i += 1
print(p * inv(q) % M)


c_mod = 1000000007

def InverseMod(b: int, m: int):
	b %= m
	if b == 0 or b == 1:
		return b
	a = m
	qs = []
	while True:
		q = a // b
		r = a % b
		if r == 0:
			break
		a = b
		b = r
		qs.append(q)
	qA = 1
	qB = -qs[len(qs) - 1]
	for i in range(len(qs) - 2, -1, -1):
		t = qA
		qA = qB
		qB = qB * -qs[i] + t
	qB %= m
	if qB < 0:
		qB = m + qB
	return qB

def save_mul(a, b):
	return a * b % c_mod

class Fraction:

	def __init__(self, a: int, b: int, dBase: int, dPow: int):
		(self.a, self.b, self.dBase, self.dPow) = (a, b, dBase, dPow)

	def __add__(self, other):
		f = Fraction(self.a, self.b, self.dBase, self.dPow)
		if f.dPow > other.dPow:
			f.a += other.a * f.dBase ** (f.dPow - other.dPow)
			f.a %= c_mod
		elif f.dPow < other.dPow:
			f.a = f.a * f.dBase ** (other.dPow - f.dPow) + other.a
			f.b = other.b
			f.dPow = other.dPow
			f.a %= c_mod
		else:
			f.a += other.a
			f.a %= c_mod
		return f

	def __mul__(self, other):
		f = Fraction(self.a, self.b, self.dBase, self.dPow)
		f.a *= other.a
		f.b *= other.b
		f.dPow += other.dPow
		f.a %= c_mod
		f.b %= c_mod
		return f

	def __str__(self):
		return '{0}/{1}'.format(self.a, self.b)

def main():
	s = str(input()).split()
	(n, m) = (int(s[0]), int(s[1]))
	s1 = str(input()).split()
	s2 = str(input()).split()
	r = Fraction(0, 1, m, 0)
	k = Fraction(1, 1, m, 0)
	for i in range(n):
		u = int(s1[i])
		d = int(s2[i])
		if u == 0 and d == 0:
			f = Fraction(int(m * (m - 1) / 2), m * m, m, 2)
			f = f * k
			r = r + f
			k.b = save_mul(k.b, m)
			k.dPow += 1
			continue
		elif u == 0:
			f = Fraction(m - d, m, m, 1)
			f = f * k
			r = r + f
			k.b = save_mul(k.b, m)
			k.dPow += 1
			continue
		elif d == 0:
			f = Fraction(u - 1, m, m, 1)
			f = f * k
			r = r + f
			k.b = save_mul(k.b, m)
			k.dPow += 1
			continue
		if u > d:
			r = r + k
		if u != d:
			break
	print(save_mul(r.a, InverseMod(r.b, c_mod)))
main()


(n, m) = list(map(int, input().split(' ')))
s1 = list(map(int, input().split(' ')))
s2 = list(map(int, input().split(' ')))
N = 10 ** 9 + 7
res = True
inv = pow(m, N - 2, N)
cur = 1
result = 0
inv_2 = pow(2, N - 2, N)
for i in range(n):
	if s1[i] == 0 and s2[i] == 0:
		result = (result + cur * inv_2 * (N + 1 - inv)) % N
		cur = cur * inv % N
		continue
	if s1[i] == 0:
		cur = cur * inv % N
		result = (result + (m - s2[i]) * cur) % N
		continue
	if s2[i] == 0:
		cur = cur * inv % N
		result = (result + (s1[i] - 1) * cur) % N
		continue
	if s1[i] < s2[i]:
		break
	if s1[i] > s2[i]:
		result = (result + cur) % N
		break
print(result % N)


def _pow(a, d, md):
	res = 1
	a = a % md
	while d > 0:
		if d & 1:
			res = res * a % md
		d >>= 1
		a = a * a % md
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 1000000007
p = 1
q = 1
dp = [[0 for i in range(n + 1)] for j in range(2)]
base = 1
dp[0][-1] = 1
dp[1][-1] = 0
for i in range(0, n):
	if a[i] == 0 and b[i] != 0:
		dp[0][i] = dp[0][i - 1] % mod
		dp[1][i] = (dp[1][i - 1] * m + dp[0][i - 1] * (m - b[i])) % mod
		base *= m
		base %= mod
	elif a[i] != 0 and b[i] == 0:
		dp[0][i] = dp[0][i - 1] % mod
		dp[1][i] = (dp[1][i - 1] * m + dp[0][i - 1] * (a[i] - 1)) % mod
		base *= m
		base %= mod
	elif a[i] == 0 and b[i] == 0:
		dp[0][i] = dp[0][i - 1] * m % mod
		dp[1][i] = dp[1][i - 1] * m * m % mod
		dp[1][i] += dp[0][i - 1] * (m - 1) * m // 2 % mod
		base *= m * m
		base %= mod
	elif a[i] != 0 and b[i] != 0:
		if a[i] != b[i]:
			dp[0][i] = 0
			dp[1][i] = dp[1][i - 1] % mod
			if a[i] > b[i]:
				dp[1][i] += dp[0][i - 1] % mod
		else:
			dp[0][i] = dp[0][i - 1] % mod
			dp[1][i] = dp[1][i - 1] % mod
p = dp[1][n - 1]
q = base
p %= mod
q %= mod
q = _pow(q, mod - 2, mod)
print(p * q % mod)


import math
mod = int(1000000000.0 + 7)
inv = [0, 1]
s = input().split()
n = int(s[0])
m = int(s[1])
B = 0
E = 1
s1 = input().split()
s2 = input().split()
for i in range(2, 2 * m + 1):
	inv.append(math.ceil(-mod / i) * inv[mod % i] % mod)

def frac(a, b):
	return a * inv[b] % mod
for i in range(n):
	ai = int(s1[i])
	bi = int(s2[i])
	if ai != 0 and bi != 0 and (ai != bi):
		if ai > bi:
			print((B + E) % mod)
		else:
			print(B % mod)
		exit(0)
	elif ai == 0 and bi == 0:
		B = (B + E * frac(m - 1, 2 * m)) % mod
		E = E * frac(1, m) % mod
	elif ai == 0 and bi != 0:
		B = (B + E * frac(m - bi, m)) % mod
		E = E * frac(1, m) % mod
	elif ai != 0 and bi == 0:
		B = (B + E * frac(ai - 1, m)) % mod
		E = E * frac(1, m) % mod
print(B % mod)


mod = 1000000007

def pow(a, b, c):
	n = 1
	m = a
	v = b
	if a == 1:
		return 1
	while v > 0:
		if v % 2 == 1:
			n *= m % c
			n %= c
		m *= m
		m %= c
		v //= 2
	return n % c
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
z = [0 for i in range(n + 10)]
for i in range(n)[::-1]:
	z[i] = z[i + 1]
	if a[i] == 0:
		z[i] += 1
	if b[i] == 0:
		z[i] += 1
ans = 0
cmb = 1
if z[0] == 0:
	if a > b:
		print(1)
	else:
		print(0)
	quit()
inverse_two = pow(2, mod - 2, mod)
com = m * (m - 1) % mod * inverse_two % mod
for i in range(n):
	if a[i] != 0 and b[i] != 0:
		if a[i] > b[i]:
			ans += cmb * pow(m, z[i + 1], mod) % mod
		break
	elif a[i] == 0 and b[i] == 0:
		ans += cmb * com % mod * pow(m, z[i + 1], mod) % mod
		cmb *= m
		cmb %= mod
	elif a[i] == 0:
		ans += cmb * (m - b[i]) % mod * pow(m, z[i + 1], mod) % mod
	elif b[i] == 0:
		ans += cmb * (a[i] - 1) % mod * pow(m, z[i + 1], mod) % mod
	ans %= mod
k = pow(m, z[0], mod)
k = pow(k, mod - 2, mod)
ans *= k
ans %= mod
print(ans)


def rev(a, m):
	res = 1
	k = m - 2
	s = a
	while k > 0:
		if k % 2 == 1:
			res = res * s % m
		k //= 2
		s = s ** 2 % m
	return res
(n, m) = [int(x) for x in input().split()]
a1 = [int(x) for x in input().split()]
a2 = [int(x) for x in input().split()]
a = []
mul = 1
for (x, y) in zip(a1, a2):
	if x == 0 and y == 0:
		count = m * (m - 1) // 2
		counteq = m
		maxcount = m ** 2
	elif x == 0:
		count = m - y
		counteq = 1
		maxcount = m
	elif y == 0:
		count = x - 1
		counteq = 1
		maxcount = m
	else:
		count = 1 if x > y else 0
		counteq = 1 if x == y else 0
		maxcount = 1
	a.append((count, counteq, maxcount))
	if counteq == 0:
		break
a.reverse()
(P, Q) = (0, 1)
for (c, ce, mc) in a:
	P = (P * ce + Q * c) % (10 ** 9 + 7)
	Q = Q * mc % (10 ** 9 + 7)
(res, zeros) = (P, Q)
print(res * rev(zeros, 10 ** 9 + 7) % (10 ** 9 + 7))


def f():
	global MOD, ans, factor
	ans %= MOD
	factor %= MOD
MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
reverse = pow(m, MOD - 2, MOD)
reverse_for_2 = (MOD + 1) // 2
ans = 0
factor = 1
for (a, b) in zip(a, b):
	if a == b == 0:
		ans += factor * ((m - 1) * (reverse * reverse_for_2))
		factor *= reverse
		f()
	elif a == 0:
		ans += factor * (m - b) * reverse
		factor *= reverse
		f()
	elif b == 0:
		ans += factor * (a - 1) * reverse
		factor *= reverse
		f()
	elif a > b:
		ans += factor
		f()
		break
	elif a == b:
		pass
	elif a < b:
		break
f()
print(ans)


MOD = 10 ** 9 + 7
(n, m) = [int(x) for x in input().split()]
s1 = [int(x) for x in input().split()]
s2 = [int(x) for x in input().split()]
mi = pow(m, MOD - 2, MOD)
m2 = pow(2, MOD - 2, MOD)
ans = 0
mul = 1
for (a, b) in zip(s1, s2):
	if a == 0 and b == 0:
		ans = (ans + mul * ((m - 1) * (mi * m2))) % MOD
		mul = mul * mi % MOD
	elif a == 0:
		ans = (ans + mul * (m - b) * mi) % MOD
		mul = mul * mi % MOD
	elif b == 0:
		ans = (ans + mul * (a - 1) * mi) % MOD
		mul = mul * mi % MOD
	elif a > b:
		ans = (ans + mul * 1) % MOD
		break
	elif a == b:
		pass
	elif a < b:
		break
print(ans % MOD)


from fractions import gcd

def add(a, b, c, d):
	lcm = b * d // gcd(b, d)
	aa = lcm // b
	bb = lcm // d
	aa = aa * a
	bb = bb * c
	cc = aa + bb
	dd = gcd(lcm, cc)
	lcm = lcm // dd
	cc = cc // dd
	return (cc, lcm)

def mul(a, b, c, d):
	aa = a * c
	bb = b * d
	dd = gcd(aa, bb)
	aa = aa // dd
	bb = bb // dd
	return (aa, bb)

def eeuclid(a, b):
	q = a // b
	r = a % b
	if r == 1:
		return (1, -q)
	(a, b) = eeuclid(b, r)
	m = 1
	n = -q
	m = m * b
	n = n * b
	n = n + a
	return (m, n)

def mod_inverse(val, m):
	(a, b) = eeuclid(val, m)
	return a % m
(n, m) = input().split()
n = int(n)
m = int(m)
mod_val = 1000000007
arr1 = []
arr2 = []
arr1 = [int(x) for x in input().split()]
arr2 = [int(x) for x in input().split()]
num = []
den = []
prob = []
for i in range(0, n):
	num.append(0)
	den.append(0)
	prob.append(0)
num.append(0)
den.append(1)
prob.append(0)
for i in range(n - 1, -1, -1):
	if arr1[i] != 0 and arr2[i] != 0:
		if arr1[i] > arr2[i]:
			prob[i] = 1
		elif arr1[i] == arr2[i]:
			if prob[i + 1] == 0:
				prob[i] = 0
			else:
				prob[i] = prob[i + 1]
		elif arr1[i] < arr2[i]:
			prob[i] = 0
	elif arr1[i] == 0 and arr2[i] != 0:
		num1 = m - arr2[i]
		inv1 = mod_inverse(m, mod_val)
		inv1 = inv1 % mod_val
		qq = num1 % mod_val * (inv1 % mod_val) % mod_val
		pp = inv1 * prob[i + 1]
		prob[i] = (qq + pp) % mod_val
	elif arr1[i] != 0 and arr2[i] == 0:
		num1 = arr1[i] - 1
		inv1 = mod_inverse(m, mod_val)
		qq = num1 % mod_val * (inv1 % mod_val) % mod_val
		pp = inv1 * prob[i + 1]
		prob[i] = (qq + pp) % mod_val
	else:
		aa = m * (m - 1) // 2
		aa = aa % mod_val
		inv2 = mod_inverse(m * m, mod_val)
		inv1 = mod_inverse(m, mod_val)
		qq = aa * inv2 % mod_val
		pp = inv1 * prob[i + 1] % mod_val
		prob[i] = (pp + qq) % mod_val
print(prob[0])


(n, m) = [int(x) for x in input().split()]
s1 = [int(x) for x in input().split()]
s2 = [int(x) for x in input().split()]
mod = int(1000000000.0 + 7)
e = 1
mi = pow(m, mod - 2, mod)
mi2 = pow(2 * m, mod - 2, mod)
res = 0
for i in range(n):
	if s1[i] == 0 and s2[i] != 0:
		res += (m - s2[i]) * mi % mod * e % mod
		e = e * mi % mod
	elif s1[i] != 0 and s2[i] == 0:
		res += (s1[i] - 1) * mi % mod * e % mod
		e = e * mi % mod
	elif s1[i] == 0 and s2[i] == 0:
		res += (m - 1) * mi2 % mod * e % mod
		e = e * mi % mod
	else:
		if s1[i] > s2[i]:
			res += e
			break
		if s1[i] < s2[i]:
			break
	res = res % mod
print(res % mod)


import sys, math
f = sys.stdin

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return None
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) ** 2
	if y & 1 == 1:
		p *= x
	return p % m

def gcd(a, b):
	while a != 0:
		t = b % a
		b = a
		a = t
	return b
(n, m) = map(int, f.readline().split())
s1 = map(int, f.readline().split())
s2 = map(int, f.readline().split())
pos = [1, 0]
all_pos = 1
for (a1, a2) in zip(s1, s2):
	next_pos = [0, 0]
	if a1 == 0 and a2 == 0:
		next_pos[0] += pos[0] * m
		next_pos[1] += pos[0] * m * (m - 1) // 2
		next_pos[1] += pos[1] * m * m
		all_pos *= m * m
	elif a1 == 0:
		next_pos[0] += pos[0]
		next_pos[1] += pos[0] * (m - a2)
		next_pos[1] += pos[1] * m
		all_pos *= m
	elif a2 == 0:
		next_pos[0] += pos[0]
		next_pos[1] += pos[0] * (a1 - 1)
		next_pos[1] += pos[1] * m
		all_pos *= m
	else:
		if a1 > a2:
			next_pos[1] += pos[0]
		elif a1 == a2:
			next_pos[0] += pos[0]
		next_pos[1] += pos[1]
	pos = next_pos
	if pos[0] == 0:
		break
	g = gcd(pos[0], all_pos)
	g = gcd(pos[1], g)
	pos[0] //= g
	pos[1] //= g
	all_pos //= g
	pos[0] %= 1000000007
	pos[1] %= 1000000007
	all_pos %= 1000000007
p = pos[1]
q = all_pos
pq_gcd = gcd(p, q)
p //= pq_gcd
q //= pq_gcd
q_inv = modInverse(q, 1000000007)
print(p * q_inv % 1000000007)


def fast(a, b):
	if b == 0:
		return 1
	if b % 2 == 1:
		return a * fast(a, b - 1) % mod
	x = fast(a, b / 2) % mod
	return x * x % mod
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = 0
q = 1
z1 = 1
z2 = 1
mod = 1000000007
for i in range(0, n):
	if a[i] != 0 and b[i] != 0:
		if a[i] == b[i]:
			continue
		if a[i] > b[i]:
			p = (p * z2 % mod + q * z1 % mod) % mod
			q = q * z2 % mod
		break
	if a[i] == 0 and b[i] != 0:
		p = (p * m * z2 % mod + z1 * q * (m - b[i]) % mod) % mod
		q = q * z2 * m % mod
		z2 = z2 * m % mod
	if a[i] != 0 and b[i] == 0:
		p = (p * m * z2 % mod + z1 * q * (a[i] - 1) % mod) % mod
		q = q * z2 * m % mod
		z2 = z2 * m % mod
	if a[i] == 0 and b[i] == 0:
		p = (p * m * 2 * z2 + z1 * q * (m - 1)) % mod
		q = q * z2 * 2 * m % mod
		z2 = z2 * m % mod
print(p * (fast(q, mod - 2) % mod) % mod)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
sys.setrecursionlimit(300000)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class BinaryTrie:

	class Node:

		def __init__(self, bit: bool=False):
			self.bit = bit
			self.children = []
			self.count = 0
			self.counter = 1

	def __init__(self, size):
		self.root = BinaryTrie.Node()
		self.size = size

	def convert(self, key):
		bits = []
		if isinstance(key, int):
			key = bin(key)[2:]
		if isinstance(key, str):
			for i in range(self.size - len(key)):
				bits += [False]
			for i in key:
				if i == '0':
					bits += [False]
				else:
					bits += [True]
		else:
			return list(key)
		return bits

	def add(self, key):
		node = self.root
		bits = self.convert(key)
		for bit in bits:
			found_in_child = False
			for child in node.children:
				if child.bit == bit:
					child.counter += 1
					node = child
					found_in_child = True
					break
			if not found_in_child:
				new_node = BinaryTrie.Node(bit)
				node.children.append(new_node)
				node = new_node
		node.count += 1

	def remove(self, key):
		node = self.root
		bits = self.convert(key)
		nodelist = [node]
		for bit in bits:
			for child in node.children:
				if child.bit == bit:
					node = child
					node.counter -= 1
					nodelist.append(node)
					break
		node.count -= 1
		if not node.children and (not node.count):
			for i in range(len(nodelist) - 2, -1, -1):
				nodelist[i].children.remove(nodelist[i + 1])
				if nodelist[i].children or nodelist[i].count:
					break

	def query(self, prefix, root=None):
		if not root:
			root = self.root
		node = root
		if not root.children:
			return 0
		for bit in prefix:
			bit_not_found = True
			for child in node.children:
				if child.bit == bit:
					bit_not_found = False
					node = child
					break
			if bit_not_found:
				return 0
		return node

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.data = 0
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key, val):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
			pCrawl.data += val
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		c = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return c
			c += 1
			pCrawl = pCrawl.children[index]
		return c

	def present(self, key):
		ans = 0
		pCrawl = self.root
		length = len(key)
		c = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
			ans += pCrawl.data
		if pCrawl != None:
			return ans
		return -1
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = 0
c = 0
k = 0
er = 0
ind = n
qw = 0
for i in range(n):
	if t[i] == 0 or s[i] == 0:
		qw = 1
	if s[i] > t[i] and t[i] != 0:
		er = 1
		ind = i
		break
	elif t[i] > s[i] and s[i] != 0:
		ind = i
		break
er1 = 0
if qw == 0:
	print(er)
	sys.exit(0)
for i in range(ind):
	if i == ind - 1:
		er1 = er
	if s[i] != 0 and t[i] != 0:
		continue
	elif s[i] == 0 and t[i] != 0:
		k = 1
		ans += (m - t[i] + er1) % mod * pow(pow(m, c + 1, mod), mod - 2, mod) % mod
		ans %= mod
		c += 1
	elif t[i] == 0 and s[i] != 0:
		k = 1
		ans += (s[i] - 1 + er1) % mod * pow(pow(m, c + 1, mod), mod - 2, mod) % mod
		ans %= mod
		c += 1
	elif t[i] == 0 and s[i] == 0:
		k = 1
		ans += (m * (m - 1) // 2 + er1 * m) % mod * pow(pow(m, c + 2, mod), mod - 2, mod) % mod
		ans %= mod
		c += 1
print(ans)


def modinverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x += m0
	return x
M = 10 ** 9 + 7
line = [int(x) for x in input().split()]
n = line[0]
m = line[1]
Mi = modinverse(m, M)
Ti = modinverse(2, M)
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
Pkp1 = 0
Pk = 0
if a[-1] == 0 and b[-1] == 0:
	Pkp1 = (m - 1) % M * Mi * Ti
elif a[-1] == 0:
	Pkp1 = (m - b[-1]) % M * Mi
elif b[-1] == 0:
	Pkp1 = (a[-1] - 1) % M * Mi
elif a[-1] > b[-1]:
	Pkp1 = 1
else:
	Pkp1 = 0
Pk = Pkp1
for i in range(1, n):
	j = n - (i + 1)
	if a[j] == 0 and b[j] == 0:
		Pk = (2 * Pkp1 + m - 1) % M * Mi * Ti
	elif a[j] == 0:
		Pk = (m - b[j] + Pkp1) % M * Mi
	elif b[j] == 0:
		Pk = (Pkp1 + a[j] - 1) % M * Mi
	elif a[j] > b[j]:
		Pk = 1
	elif a[j] < b[j]:
		Pk = 0
	else:
		Pk = Pkp1
	Pkp1 = Pk
print(Pk % M)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	dp = [[0, 0, 0] for i in range(n + 1)]
	dp[0][0] = 1
	for (i, (a, b)) in enumerate(zip(A, B)):
		if a != 0 and b != 0:
			if a > b:
				dp[i + 1][1] += dp[i][1]
				dp[i + 1][2] += dp[i][0] + dp[i][2]
			elif a == b:
				dp[i + 1][0] += dp[i][0]
				dp[i + 1][1] += dp[i][1]
				dp[i + 1][2] += dp[i][2]
			else:
				dp[i + 1][1] += dp[i][0] + dp[i][1]
				dp[i + 1][2] += dp[i][2]
		elif a == 0 and b == 0:
			dp[i + 1][0] = dp[i][0] * m
			dp[i + 1][1] = dp[i][1] * m ** 2 + dp[i][0] * ((m ** 2 - m) // 2)
			dp[i + 1][2] = dp[i][2] * m ** 2 + dp[i][0] * ((m ** 2 - m) // 2)
		elif a == 0 and b != 0:
			dp[i + 1][0] = dp[i][0]
			dp[i + 1][1] = dp[i][1] * m + dp[i][0] * (b - 1)
			dp[i + 1][2] = dp[i][2] * m + dp[i][0] * (m - b)
		elif a != 0 and b == 0:
			dp[i + 1][0] = dp[i][0]
			dp[i + 1][1] = dp[i][1] * m + dp[i][0] * (m - a)
			dp[i + 1][2] = dp[i][2] * m + dp[i][0] * (a - 1)
		dp[i + 1][0] %= mod
		dp[i + 1][1] %= mod
		dp[i + 1][2] %= mod
	x = sum(dp[-1])
	y = dp[-1][2]
	ans = y * pow(x, mod - 2, mod)
	print(ans % mod)
main()


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

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

	def readString(self):
		while self.pos == len(self.buf):
			self.readToBuffer()
		ans = self.buf[self.pos]
		self.pos += 1
		return ans

	def readInt(self):
		return int(self.readString())

	def readFloat(self):
		return float(self.readString())

	def readStringArray(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.readString())
		return arr

	def readIntArray(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.readInt())
		return arr

	def readFloatArray(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.readFloat())
		return arr

	def readLine(self):
		while self.pos == len(self.buf):
			self.readToBuffer()
		if self.pos > 0:
			raise ValueError('Cannot call readline in the middle of a line.')
		return self.raw

	def print(self, s):
		self.output.write(str(s))

	def println(self, s):
		self.print(s)
		self.print('\n')

	def flushOutput(self):
		self.output.flush()
pythonIO = IO(sys.stdin, sys.stdout)
solve(pythonIO)
pythonIO.flushOutput()


MOD = 1000000007
(n, m) = map(int, input().split())
l1 = [int(x) for x in input().split()]
l2 = [int(x) for x in input().split()]
probLeft = 1

def modInv(x, n=MOD - 2):
	if n <= 1:
		return x ** n % MOD
	tmp = modInv(x, n // 2) ** 2 % MOD
	if n % 2 == 1:
		tmp = tmp * x % MOD
	return tmp
dp = {}

def fraction(x, y):
	if (x, y) in dp:
		return dp[x, y]
	dp[x, y] = x * modInv(y) % MOD
	return dp[x, y]
minv = fraction(1, m)
ans = 0
for i in range(n):
	a = l1[i]
	b = l2[i]
	if a == 0 or b == 0:
		if b > 0:
			ans += probLeft * (m - b) * minv % MOD
		elif a > 0:
			ans += probLeft * (a - 1) * minv % MOD
		else:
			ans += probLeft * ((m - 1) * m // 2) * minv * minv % MOD
		probLeft = probLeft * minv % MOD
	elif a > b:
		ans += probLeft
		break
	elif a == b:
		continue
	else:
		break
print(ans % MOD)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = int(1000000000.0 + 7)
m2 = pow(2, MOD - 2, MOD)
mm = pow(m, MOD - 2, MOD)
f = 1
ans = 0
for (i, j) in zip(a, b):
	if i == 0 and j == 0:
		ans += (m - 1) * m2 * mm * f
		ans %= MOD
		f = f * mm % MOD
	elif i == 0:
		ans += (m - j) * f * mm
		ans %= MOD
		f = f * mm % MOD
	elif j == 0:
		ans += (i - 1) * f * mm
		ans %= MOD
		f = f * mm % MOD
	elif i > j:
		ans += f
		ans %= MOD
		break
	elif i < j:
		break
print(ans)


(n, m) = map(int, input().split())
s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7
(p, q) = (0, 1)
for i in reversed(range(n)):
	if s1[i] == 0 and s2[i] == 0:
		p = (q * (m - 1) + 2 * p) % MOD
		q = 2 * m * q % MOD
	elif s1[i] == 0:
		p = (q * (m - s2[i]) + p) % MOD
		q = m * q % MOD
	elif s2[i] == 0:
		p = (q * (s1[i] - 1) + p) % MOD
		q = m * q % MOD
	elif s1[i] < s2[i]:
		(p, q) = (0, 1)
	elif s1[i] > s2[i]:
		(p, q) = (1, 1)

def mpow(a, n):
	if n == 0:
		return 1
	t = mpow(a, n // 2)
	t = t * t % MOD
	if n % 2 == 1:
		t = t * a % MOD
	return t
inv_q = mpow(q, MOD - 2)
r = p * inv_q % MOD
print(r)


def main():
	(n, m) = map(int, input().split())
	S1 = list(map(int, input().split()))
	S2 = list(map(int, input().split()))
	p = 0
	q = 1
	mod = 1000000007
	prbq = 1
	for i in range(0, n):
		if S1[i] == S2[i]:
			if S1[i] == 0:
				p = (p * prbq * 2 * m + q * (m - 1)) % mod
				q = q * prbq * 2 * m % mod
				prbq = prbq * m % mod
			continue
		elif S1[i] > S2[i]:
			if S2[i] != 0:
				p = (p * prbq + q) % mod
				q = q * prbq % mod
				break
			p = (p * m * prbq + q * (S1[i] - 1)) % mod
			q = q * prbq * m % mod
			prbq = prbq * m % mod
		else:
			if S1[i] != 0:
				break
			p = (p * m * prbq + q * (m - S2[i])) % mod
			q = q * prbq * m % mod
			prbq = prbq * m % mod
	print(p * pow(q, mod - 2, mod) % mod)
main()


(n, m) = map(int, input().split())
MOD = 10 ** 9 + 7
S1 = list(map(int, input().split()))
S2 = list(map(int, input().split()))

def rev(X):
	return pow(X, MOD - 2, MOD)
nume = 0
deno = pow(m, S1.count(0) + S2.count(0), MOD)
dp = [0] * (n + 1)
dp[0] = deno
for i in range(n):
	(num_s1, num_s2) = (S1[i], S2[i])
	if num_s1 == 0 and num_s2 == 0:
		unit = dp[i] * rev(m * m)
		dp[i + 1] = unit * m % MOD
		nume += m * (m - 1) // 2 * unit
		continue
	elif num_s1 == 0:
		unit = dp[i] * rev(m) % MOD
		nume += (m - num_s2) * unit
		dp[i + 1] = unit
		continue
	elif num_s2 == 0:
		unit = dp[i] * rev(m) % MOD
		nume += (num_s1 - 1) * unit
		dp[i + 1] = unit
		continue
	else:
		unit = dp[i]
		if num_s1 == num_s2:
			dp[i + 1] = unit
			continue
		elif num_s1 < num_s2:
			dp[i + 1] = 0
		elif num_s1 > num_s2:
			dp[i + 1] = 0
			nume += unit
		continue
nume %= MOD
ans = nume * rev(deno) % MOD
print(ans)