Chef is given two binary strings A and B, each having length N.

Chef wants to find the number of binary strings C, of length N, such that H(A, C) = H(B, C), where H(X, Y) denotes the *hamming distance* between the strings X and Y.

Since the answer can be large, output it modulo 10^{9}+7.

Note: [Hamming distance] between two strings of equal length is the number of positions at which the corresponding characters are different.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the length of the strings.
- The second line contains the binary string A.
- The third line contains the binary string B.

------ Output Format ------ 

For each test case, output in a new line, the number of binary strings C which satisfy the given conditions modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$A$ and $B$ consist of $0$ and $1$ only.
- Sum of $N$ over all test cases do not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
11
00
5
10101
10101
3
101
011

----- Sample Output 1 ------ 
2
32
4

----- explanation 1 ------ 
Test case $1$: The number of strings $C$, of length $2$, such that $H(A, C) = H(B, C)$ is $2$. The strings are:
- $C = 10$: Here, $H(11, 10) = H(00, 10) = 1$, as there is only one position where the corresponding characters are different.
- $C = 01$: Here, $H(11, 01) = H(00, 01) = 1$.

Test case $3$: The number of strings $C$, of length $3$, such that $H(A, C) = H(B, C)$ is $4$. The strings are:
- $C = 000$: Here, $H(101, 000) = H(011, 000) = 2$, as there are two positions where the corresponding characters are different.
- $C = 111$: Here, $H(101, 111) = H(011, 111) = 1$, as there is only one position where the corresponding characters are different.
- $C = 001$: Here, $H(101, 001) = H(011, 001) = 1$, as there is only one position where the corresponding characters are different.
- $C = 110$: Here, $H(101, 110) = H(011, 110) = 2$, as there are two positions where the corresponding characters are different.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	m = 0
	for i in range(n):
		if a[i] == b[i]:
			m += 1
	if n - m & 1:
		print(0)
		continue
	mod = 10 ** 9 + 7
	ans = pow(2, m, mod)
	nr = 1
	dr = 1
	for i in range(1, n - m + 1):
		nr = nr * i % mod
	for i in range(1, (n - m) // 2 + 1):
		dr = dr * i % mod
	for i in range(1, (n - m) // 2 + 1):
		dr = dr * i % mod
	dr = pow(dr, -1, mod)
	print(ans * nr * dr % mod)


import math
mod = 1000000007

def fact(n):
	ans = 1
	for i in range(2, n + 1):
		ans = ans * i % mod
	return ans

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def comb(n, k):
	return modDivide(fact(n), fact(k) * fact(n - k), mod)
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	eq = 0
	no = 0
	for i in range(len(a)):
		if a[i] == b[i]:
			eq += 1
		else:
			no += 1
	if no % 2 == 1:
		print(0)
	else:
		print(pow(2, eq, mod) * comb(no, no // 2) % mod)


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	n_e = 0
	n_ue = 0
	for i in range(n):
		if a[i] == b[i]:
			n_e += 1
		else:
			n_ue += 1
	if n_ue % 2 == 1:
		print(0)
	else:
		ans_e = pow(2, n_e, m)
		ans_ue = 1
		for i in range(1, n_ue // 2 + 1):
			ans_ue = ans_ue * (n_ue - i + 1) * pow(i, -1, m)
			ans_ue %= m
		ans = ans_e * ans_ue % m
		print(int(ans))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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')
mod = 1000000007

def precompute():
	fuck[0] = factor[0] = 1
	for i in range(1, z):
		fuck[i] = nu(fuck[i - 1], i)
		factor[i] = nu(factor[i - 1], mod_inverse(i))

def nu(x, y):
	return x % mod * (y % mod) % mod

def mod_inverse(a, m=mod):
	return bp(a, m - 2)
z = 200001
fuck = [0] * z
factor = [0] * z

def bp(a, kya):
	if kya == 0:
		return 1
	arey = bp(a, kya // 2)
	arey = nu(arey, arey)
	if kya % 2:
		return nu(arey, a)
	return arey

def ans():
	puku = int(input())
	A = input()
	B = input()
	count = 0
	for i in range(puku):
		if A[i] == B[i]:
			count += 1
	if (puku - count) % 2:
		print(0)
		return
	puku -= count
	ans = bp(2, count)
	ans = nu(ans, nu(fuck[puku], nu(factor[puku // 2], factor[puku // 2])))
	print(ans)
precompute()
T = int(input())
while T:
	T -= 1
	ans()


MOD = 10 ** 9 + 7

def fact(n):
	ans = 1
	for i in range(2, n + 1):
		ans = ans * i % MOD
	return ans

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def comb(n, k):
	return modDivide(fact(n), fact(k) * fact(n - k), MOD)
t = int(input())
import math
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	n_diff = 0
	n_sim = 0
	for (c1, c2) in zip(a, b):
		if c1 == c2:
			n_sim += 1
		else:
			n_diff += 1
	if n_diff % 2 == 1:
		print(0)
	else:
		print(pow(2, n_sim, MOD) * comb(n_diff, n_diff // 2) % MOD)


md = 10 ** 9 + 7

def bcm(x, y, md):
	rv = 1
	for i in range(y):
		rv = rv * (x - i) % md
		rv = rv * pow(i + 1, -1, md) % md
	return rv
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	assert len(a) == n and len(b) == n
	z = list(zip(a, b))
	s = z.count(('0', '0')) + z.count(('1', '1'))
	d = n - s
	if d % 2 != 0:
		print(0)
	else:
		print(pow(2, s, md) * bcm(d, d // 2, md) % md)


mod = 10 ** 9 + 7

def C(n, r):
	ret = 1
	for i in range(1, r + 1):
		ret = ret * (n - i + 1) * pow(i, mod - 2, mod)
		ret %= mod
	return ret
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	differ = 0
	for i in range(n):
		differ += a[i] != b[i]
	if differ % 2 == 1:
		print(0)
	else:
		print(pow(2, n - differ, mod) * C(differ, differ // 2) % mod)


from math import comb
mod = 10 ** 9 + 7

def c(n, r):
	ret = 1
	for i in range(1, r + 1):
		ret = ret * (n - i + 1) * pow(i, -1, mod)
		ret %= mod
	return int(ret)
for i in range(int(input())):
	s = int(input())
	s1 = input()
	s2 = input()
	dif = 0
	for j in range(s):
		if s1[j] != s2[j]:
			dif += 1
	same = s - dif
	if dif % 2 == 1:
		ans = 0
	else:
		ans = c(dif, int(dif / 2)) * 2 ** same % mod
	print(ans)


import math

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)

def powermodulo(a, b, mod):
	res = 1 % mod
	while b > 0:
		if b & 1 != 0:
			res = res % mod * a % mod % mod
		a = a % mod * a % mod % mod
		b = b >> 1
	return res
case = int(input())
md = 1000000007
for _ in range(case):
	n = int(input())
	a = input()
	b = input()
	count = 0
	for i in range(n):
		if a[i] != b[i]:
			count += 1
	res = 0
	if count % 2 == 0:
		same = n - count
		ans = powermodulo(2, same, md)
		res = ans % md * nCr(count, count // 2) % md % md
	print(res)


import math
test = int(input())
for _ in range(test):
	n = int(input())
	s1 = input()
	s2 = input()
	diff = 0
	same = 0
	for i in range(n):
		if s1[i] != s2[i]:
			diff += 1
		else:
			same += 1
	if diff % 2 != 0:
		print(0)
	else:
		first = 2 ** same % 1000000007
		second = math.factorial(diff) // (math.factorial(diff // 2) * math.factorial(diff // 2))
		ans = first * second % 1000000007
		print(ans)


from math import factorial

def combination(n, r):
	num = factorial(n)
	den = factorial(n - r) * factorial(r)
	return num // den

def solve(a, b):
	not_matching = 0
	matching = 0
	for x in range(len(a)):
		if a[x] == b[x]:
			matching += 1
		else:
			not_matching += 1
	if not_matching % 2 == 0 and not_matching != 0:
		return combination(not_matching, not_matching // 2) * 2 ** matching
	elif not_matching == 0:
		return 2 ** matching
	else:
		return 0
out = []
t = int(input())
for x in range(t):
	n = int(input())
	a = input()
	b = input()
	out.append(solve(a, b))
for var in out:
	print(var % 1000000007)


def fact(n):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i % 1000000007
	return ans

def ncr(n, r):
	a = 1
	b = 1
	for i in range(1, n + 1):
		if i <= n // 2:
			a *= i
		else:
			b *= i
	return b // a
t = int(input())
for tc in range(t):
	n = int(input())
	a = input()
	b = input()
	d = 0
	for i in range(n):
		if a[i] != b[i]:
			d += 1
	s = n - d
	if d % 2 == 1:
		print('0')
	else:
		ans = 2 ** s % (10 ** 9 + 7)
		ans = ans * (ncr(d, d // 2) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		print(int(ans) % (10 ** 9 + 7))


modn = 1000000007
factorials = [0, 1]
for i in range(2, 200001):
	factorials.append(factorials[i - 1] * i % modn)
for _ in range(int(input())):
	N = int(input())
	A = input()
	B = input()
	same = 0
	for i in range(N):
		if A[i] == B[i]:
			same += 1
	diff = N - same
	if diff % 2 == 1:
		print('0')
	else:
		if diff == 0:
			answ = 1
		else:
			halfDiff = diff // 2
			answ = factorials[diff]
			multinv = pow(factorials[halfDiff], modn - 2, modn)
			answ = answ * multinv % modn
			answ = answ * multinv % modn
		answ = answ * pow(2, same, modn) % modn
		print(answ)


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	NnN = 0
	NnN1 = 0
	AmmYvT = 0
	for i in range(n):
		if a[i] == b[i]:
			NnN += 1
		else:
			NnN1 += 1
	if NnN1 % 2 == 1:
		print(0)
	else:
		NnN2 = pow(2, NnN, m)
		NnN3 = 1
		for i in range(1, NnN1 // 2 + 1):
			NnN3 = NnN3 * (NnN1 - i + 1) * pow(i, -1, m)
			NnN3 %= m
		ans = NnN2 * NnN3 % m
		print(int(ans))


def fact(n):
	d = 1
	m = 1
	k = n // 2
	for i in range(k):
		d = d * (n - i) % (10 ** 9 + 7)
		d = d * pow(i + 1, -1, 10 ** 9 + 7) % (10 ** 9 + 7)
	return d
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	c = 0
	for i in range(n):
		if a[i] == b[i]:
			c = c + 1
	k = n - c
	if (n - c) % 2 == 1:
		print('0')
	else:
		ans = pow(2, c, 10 ** 9 + 7) * fact(k) % (10 ** 9 + 7)
		print(ans)


import math
t = int(input())
p = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	if a == b:
		print(2 ** n % p)
	else:
		unc = 0
		for j in range(n):
			if a[j] != b[j]:
				unc += 1
		if unc % 2 == 1:
			print(0)
		else:
			print(math.factorial(unc) // math.factorial(unc // 2) ** 2 * 2 ** (n - unc) % p)


import math

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -1
	else:
		return inv * a % m
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	s = 0
	d = 0
	for i in range(n):
		if a[i] == b[i]:
			s += 1
		else:
			d += 1
	if d % 2 == 1:
		print(0)
		continue
	ans = 1
	denom = 1
	dd = d // 2
	for i in range(dd):
		ans = ans * (d - i) % 1000000007
		denom = denom * (i + 1)
	ans = modDivide(ans, denom, 1000000007)
	ans2 = pow(2, s, 1000000007)
	ans = ans * ans2 % 1000000007
	print(ans)


M = 1000000007

def pow(a, n, m=1000000007):
	ans = 1
	while n:
		if n & 1:
			ans = ans * a % m
		a = a * a % m
		n >>= 1
	return ans
fact = [1, 1]
for i in range(2, 200001):
	fact.append(fact[-1] * i % M)
for t in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	s = d = 0
	for i in range(n):
		if a[i] == b[i]:
			s += 1
		else:
			d += 1
	if d & 1:
		print(0)
		continue
	ans = (1 << s) % M * (fact[d] % M) * (pow(fact[d // 2] % M, M - 2) % M) ** 2 % M
	print(int(ans))


from math import factorial
mod = 10 ** 9 + 7
ncr = lambda n, r: factorial(n) // (factorial(r) * factorial(n - r))

def soln(n, a, b):
	matches = uns = 0
	for i in range(n):
		if a[i] != b[i]:
			uns += 1
		else:
			matches += 1
	if uns & 1:
		return 0
	sems = pow(2, matches, mod)
	return sems * (ncr(uns, uns // 2) % mod) % mod
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	print(soln(n, a, b))


def fact(n):
	(a, b) = (1, 1)
	for i in range(1, n + 1):
		if i <= n // 2:
			a *= i
		else:
			b *= i
	return b // a
q = int(input())
while q:
	q -= 1
	n = int(input())
	s = input()
	t = input()
	(diff, same) = (0, 0)
	for i in range(n):
		if s[i] == t[i]:
			same += 1
		else:
			diff += 1
	if diff % 2:
		print(0)
		continue
	same = (1 << same) % (10 ** 9 + 7)
	v = fact(diff) % (10 ** 9 + 7)
	same *= v
	print(same % (10 ** 9 + 7))


p = 10 ** 9 + 7

def bin(x, y, p):
	rv = 1
	for i in range(y):
		rv = rv * (x - i) % p
		rv = rv * pow(i + 1, -1, p) % p
	return rv
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = 0
	for (i, j) in zip(a, b):
		if i == j:
			c += 1
	d = n - c
	if d % 2 != 0:
		print(0)
	else:
		print(pow(2, c, p) * bin(d, d // 2, p) % p)


import math

def C(n, r):
	ret = 1
	for i in range(1, r + 1):
		ret = ret * (n - i + 1) * pow(i, mod - 2, mod)
		ret %= mod
	return ret

def count_possibilities(n, a, b, mod):
	differ = 0
	for i in range(n):
		differ += a[i] != b[i]
	if differ % 2 == 1:
		return 0
	else:
		return pow(2, n - differ, mod) * C(differ, differ // 2) % mod
t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	print(count_possibilities(n, a, b, mod))


from math import factorial
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	same = diff = 0
	for i in range(n):
		if a[i] == b[i]:
			same += 1
	diff = n - same
	if diff % 2 == 1:
		print(0)
	else:
		nn = diff
		rr = diff // 2
		fact = factorial(nn) // (factorial(nn - rr) * factorial(rr))
		ans = 2 ** same * fact % mod
		print(ans)


t = int(input())

def ncr(n, r):
	res = 1
	for i in range(n, n - r, -1):
		res *= i
	d = 1
	for i in range(r, 1, -1):
		d *= i
	return res // d
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	diff = 0
	m = 10 ** 9 + 7
	for i in range(n):
		diff += a[i] != b[i]
	if diff % 2:
		print(0)
	else:
		print(pow(2, n - diff, m) * ncr(diff, diff // 2) % m)


import math
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	not_same = 0
	ans = 1
	for i in range(n):
		if a[i] != b[i]:
			not_same += 1
		else:
			ans = ans * 2
	if not_same % 2 == 0 and not_same != 0:
		temp1 = math.factorial(not_same)
		temp2 = math.factorial(not_same / 2)
		ans = ans * temp1 // (temp2 * temp2)
	if not_same % 2 != 0:
		print(0)
	else:
		print(int(ans % 1000000007))


import math
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	not_same = 0
	lar = 1000000007
	ans = 1
	for i in range(0, len(s1)):
		if s1[i] == s2[i]:
			ans = ans * 2
		else:
			not_same = not_same + 1
	if not_same % 2 == 0 and not_same != 0:
		temp1 = math.factorial(not_same)
		temp2 = math.factorial(not_same / 2)
		ans = ans * temp1 // (temp2 * temp2)
	if not_same % 2 != 0:
		print(0)
	else:
		print(int(ans % lar))


import math

def binomial_coeff(n, k, mod):
	C = [0] * (k + 1)
	C[0] = 1
	for i in range(1, k + 1):
		C[i] = C[i - 1] * (n - (i - 1)) % mod
		C[i] = C[i] * pow(i, mod - 2, mod) % mod
	return C[k]

def count_possibilities(n, a, b, mod):
	k = 0
	for i in range(n):
		if a[i] != b[i]:
			k += 1
	if k % 2 != 0:
		return 0
	C = binomial_coeff(k, k // 2, mod)
	res = pow(2, n - k, mod)
	res = res * C % mod
	return res
t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	print(count_possibilities(n, a, b, mod))


t = int(input())
ans = []
mod = 10 ** 9 + 7

def ncr(n, r):
	ret = 1
	for i in range(1, r + 1):
		ret = ret * (n - i + 1) * pow(i, mod - 2, mod)
		ret %= mod
	return ret
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	samaan = 0
	asmaan = 0
	for i in range(n):
		if a[i] == b[i]:
			samaan += 1
		else:
			asmaan += 1
	if asmaan % 2:
		print(0)
		continue
	ans = pow(2, samaan, mod) * ncr(asmaan, asmaan // 2)
	print(ans % mod)


def ch(a, b):
	ans = 0
	for i in range(len(a)):
		ans += a[i] != b[i]
	return ans
import random as r
mod = 10 ** 9 + 7
fact = [1]
e = 2 * 10 ** 5 + 1
for i in range(1, e):
	fact.append(fact[-1] * i % mod)

def ncr(n):
	a = fact[n]
	b = fact[n // 2]
	x = pow(b * b, mod - 2, mod)
	return a * x % mod
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	ans = 0
	(x, y1, y2) = (0, 0, 0)
	for i in range(n):
		if a[i] == b[i]:
			x += 1
		elif a[i] == '1':
			y1 += 1
		else:
			y2 += 1
	if (y1 + y2) % 2:
		ans = 0
	else:
		ans = pow(2, x, mod)
		x = ncr(y1 + y2)
		ans = ans * x % mod
	print(ans)


import math
t = int(input())
mod = 10 ** 9 + 7
while t:
	t -= 1
	n = int(input())
	a = input()
	b = input()
	same = 0
	for i in range(n):
		if a[i] == b[i]:
			same += 1
	diff = n - same
	if diff % 2:
		print(0)
	else:
		res = 2 ** same % mod
		res *= math.factorial(diff) // math.factorial(diff // 2) ** 2
		print(res % mod)


import math
for i in range(int(input())):
	n = int(input())
	arr1 = input()
	arr2 = input()
	cnt = 0
	for j in range(n):
		if arr1[j] != arr2[j]:
			cnt += 1
	if cnt % 2 != 0:
		print(0)
	else:
		ans = 2 ** (n - cnt)
		ans *= math.factorial(cnt) // math.factorial(cnt // 2) ** 2
		print(ans % (10 ** 9 + 7))


import math
for i in range(int(input())):
	num = int(input())
	A = input()
	B = input()
	count = 0
	for j in range(num):
		if A[j] != B[j]:
			count += 1
	if count % 2 != 0:
		print(0)
	else:
		ans = 2 ** (num - count)
		ans *= math.factorial(count) // math.factorial(count // 2) ** 2
		print(ans % (10 ** 9 + 7))


MOD = 10 ** 9 + 7

def ncr(n, r):
	fact = [1] * (n + 1)
	for i in range(1, n + 1):
		fact[i] = fact[i - 1] * i % MOD
	res = pow(fact[r], MOD - 2, MOD)
	res *= pow(fact[n - r], MOD - 2, MOD)
	res %= MOD
	return fact[n] * res % MOD
for _ in range(int(input())):
	N = int(input())
	a = input()
	b = input()
	s = 0
	d = 0
	for i in range(N):
		if a[i] == b[i]:
			s += 1
		else:
			d += 1
	if d & 1 == 1:
		print(0)
	else:
		res = pow(2, s, MOD) * ncr(d, d // 2)
		print(res % MOD)


MOD = 10 ** 9 + 7

def mypow(num, p):
	res = 1
	while p > 0:
		if p % 2 == 1:
			res = res * num
			res %= MOD
		num = num * num % MOD
		p >>= 1
	return res

def modInv(num):
	return mypow(num, MOD - 2)

def ncr(n, r):
	fact = [1] * (n + 1)
	for i in range(2, n + 1):
		fact[i] = fact[i - 1] * i % MOD
	m = modInv(fact[r])
	inv = m * m % MOD
	return fact[n] * inv % MOD
for _ in range(int(input())):
	N = int(input())
	a = input()
	b = input()
	s = 0
	d = 0
	for i in range(N):
		if a[i] == b[i]:
			s += 1
		else:
			d += 1
	if d & 1 == 1:
		print(0)
	else:
		res = mypow(2, s) * ncr(d, d // 2)
		print(res % MOD)


import math

def fact(n):
	return math.factorial(n)

def mod(t):
	return t % 1000000007
for _ in range(int(input())):
	(N, A, B) = (mod(int(input())), input(), input())
	j = 0
	for i in range(N):
		if A[i] != B[i]:
			j += 1
	j = mod(j)
	dd = 0
	if mod(j) % 2 == 0:
		dd = mod(fact(j) // fact(j // 2) ** 2)
	print(mod(mod(2 ** (N - j)) * dd))


fact = [1]
inv_fact = [1]
mod = pow(10, 9) + 7
for _ in range(int(input())):
	n = int(input())
	A = input()
	B = input()
	dua = 0
	for i in range(n):
		if A[i] == B[i]:
			dua += 1
	beda = n - dua
	if beda % 2 == 1:
		print(0)
	else:
		ans = pow(2, dua, mod)
		while len(inv_fact) < 1 + (n - dua) // 2:
			fact.append(fact[-1] * len(fact) % mod)
			fact.append(fact[-1] * len(fact) % mod)
			inv_fact.append(inv_fact[-1] * pow(len(inv_fact), -1, mod) % mod)
		combi = fact[beda] * pow(inv_fact[beda // 2], 2, mod) % mod
		ans = ans * combi % mod
		print(ans)


mod = 10 ** 9 + 7

def comb(n):
	(upper, lower) = (1, 1)
	for i in range(1, n + 1):
		if i > n // 2:
			upper *= i
		else:
			lower *= i
	return upper // lower % mod
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	q = 0
	for i in range(n):
		if a[i] == b[i]:
			q += 1
	if (n - q) % 2:
		print(0)
		continue
	answer = (1 << q) % mod
	answer *= comb(n - q) % mod
	print(answer % mod)


import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
import heapq

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

class mydict:

	def __init__(self, func=lambda : 0):
		self.random = randint(0, 1 << 32)
		self.default = func
		self.dict = {}

	def __getitem__(self, key):
		mykey = self.random ^ key
		if mykey not in self.dict:
			self.dict[mykey] = self.default()
		return self.dict[mykey]

	def get(self, key, default):
		mykey = self.random ^ key
		if mykey not in self.dict:
			return default
		return self.dict[mykey]

	def __setitem__(self, key, item):
		mykey = self.random ^ key
		self.dict[mykey] = item

	def getkeys(self):
		return [self.random ^ i for i in self.dict]

	def __str__(self):
		return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

def lcm(a, b):
	return a * b // math.gcd(a, b)

def mod(n):
	return n % 1000000007

def power(bas, exp):
	if exp == 0:
		return 1
	if exp == 1:
		return bas
	if exp % 2 == 0:
		t = power(bas, exp // 2)
		t = mod(t * t)
		return t
	else:
		return mod(power(bas, exp - 1) * bas)
factr = []
factr = [1]
fact = 1
for i in range(1, MAXN):
	fact = mod(mod(fact) * mod(i))
	factr.append(fact)

def nCr(n, r):
	if r > n:
		return 0
	n1 = factr[n]
	d1 = power(factr[r], 1000000005)
	d2 = power(factr[n - r], 1000000005)
	return mod(mod(n1) * mod(d1) * mod(d2))

def solve(t):
	n = readInts()
	s1 = readStr()
	s2 = readStr()
	difcnt = 0
	ans = 1
	for i in range(n):
		if s1[i] == s2[i]:
			ans = mod(mod(ans) * 2)
		else:
			difcnt += 1
	if difcnt & 1:
		print(0)
		return
	ans = mod(mod(ans) * mod(nCr(difcnt, difcnt // 2)))
	print(ans)

def main():
	t = 1
	if path.exists('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt'):
		sys.stdin = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt', 'r')
		sys.stdout = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/output.txt', 'w')
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = str(input())
	b = str(input())
	cnt = 0
	for (i, j) in zip(a, b):
		if i != j:
			cnt += 1
	if cnt & 1:
		print(0)
		continue
	ans = 2 ** (n - cnt) % M
	ans *= ncr(cnt, cnt // 2, M)
	print(ans % M)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	cnt = 0
	for i in range(n):
		if a[i] != b[i]:
			cnt += 1
	if cnt % 2 != 0:
		print(0)
	else:
		ans = 1
		for i in range(n):
			if a[i] == b[i]:
				ans *= 2
		ans *= math.factorial(cnt) // math.factorial(cnt // 2) ** 2
		print(ans % 1000000007)


def fun(a, b, m):
	s = 1
	for i in range(b + 1, a + 1):
		s *= i % m
	for i in range(1, b + 1):
		s = s * pow(i, -1, m) % m
	return s
import math
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	m = 1000000007
	d = {'11': 0, '00': 0, '10': 0, '01': 0}
	for i in range(n):
		d[f'{a[i]}{b[i]}'] += 1
	p = d['10'] + d['01']
	if p % 2 == 0:
		n = d['11'] + d['00']
		s = pow(2, n, m)
		s *= fun(p, p // 2, m) % m
		print(s % m)
	else:
		print(0)


import math

def nCr(n, r):
	a = math.factorial(n)
	b = math.factorial(r)
	c = math.factorial(n - r)
	b = b * c
	a = a // b
	a = a % 1000000007
	return int(a)
test = int(input())
for tc in range(test):
	n = int(input())
	s1 = input()
	s2 = input()
	dif = 0
	same = 0
	for i in range(n):
		if s1[i] == s2[i]:
			same = same + 1
		else:
			dif = dif + 1
	if dif % 2 == 0:
		a = nCr(dif, dif // 2)
		a = a % 1000000007
		if a < 1:
			a = 1
		b = int(pow(2, same))
		ans = a * b
		ans = ans % 1000000007
		print(ans)
	else:
		print(0)


import math
md = 10 ** 9 + 7

def combination(m, n):
	temp = 1
	for i in range(m, n, -1):
		temp = temp * i
	return temp // math.factorial(n) % md

def solve(n, a, b):
	temp = bin(int(a, 2) ^ int(b, 2)).count('1')
	return pow(2, n - temp, md) * combination(temp, temp // 2) % md if temp % 2 == 0 else 0
for _ in range(int(input())):
	print(solve(int(input()), input(), input()))


mod = 10 ** 9 + 7
import math

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def nCr(n, r):
	if r > n:
		return 0
	if r == 0 or r == n:
		return 1
	return nCr(n - 1, r - 1) + nCr(n - 1, r)
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	pro = 0
	na = 0
	for i in range(n):
		if a[i] == b[i]:
			pro += 1
		else:
			na += 1
	if na % 2 == 1:
		print(0)
	else:
		shit = 1
		for i in range(pro):
			shit = 2 * shit % mod
		haaa = ncr(na, na // 2, mod)
		if na == 0:
			print(shit)
		elif pro == 0:
			print(haaa % mod)
		else:
			print(shit % mod * (haaa % mod) % mod)


from math import factorial
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = input()
	b = input()
	x = int(a, 2)
	y = int(b, 2)
	ans = 0
	if x == y:
		ans = 2 ** n
	else:
		diff = 0
		for i in range(n):
			if a[i] != b[i]:
				diff += 1
		if diff % 2:
			ans = 0
		else:
			up = factorial(diff)
			down = factorial(diff // 2)
			ans = up * 2 ** (n - diff) // (down * down)
	print(ans % (10 ** 9 + 7))


import math
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	dist = 0
	for i in range(n):
		if a[i] != b[i]:
			dist += 1
	if dist % 2 != 0:
		print(0)
		continue
	fact = math.factorial(dist) // (math.factorial(dist // 2) * math.factorial(dist // 2))
	print(fact * 2 ** (n - dist) % 1000000007)


mod = 1000000007

def hel(a, b):
	return a % mod * (b % mod) % mod

def bis(a, b):
	if b == 0:
		return 1
	temp = bis(a, b // 2)
	temp = hel(temp, temp)
	if b % 2:
		return hel(temp, a)
	return temp

def mi(a, m=mod):
	return bis(a, m - 2)
s = 2 * 10 ** 5 + 1
fact = [0] * s
ifact = [0] * s

def pc():
	fact[0] = ifact[0] = 1
	for i in range(1, s):
		fact[i] = hel(fact[i - 1], i)
		ifact[i] = hel(ifact[i - 1], mi(i))

def disolve():
	n = int(input())
	(k, j) = (input(), input())
	count = 0
	for i in range(n):
		if k[i] == j[i]:
			count += 1
	if (n - count) % 2:
		print(0)
		return
	n -= count
	flag = bis(2, count)
	flag = hel(flag, hel(fact[n], hel(ifact[n // 2], ifact[n // 2])))
	print(flag)
pc()
nothingP = int(input())
for _ in range(nothingP):
	disolve()


import math

def nCr(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = math.gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p

def ncrp(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
for _ in range(int(input())):
	n = int(input())
	(a, b) = (input(), input())
	same = 0
	for i in range(n):
		if a[i] == b[i]:
			same += 1
	diff = n - same
	ans = 0
	if diff % 2 == 1:
		ans = 0
	elif diff == 0:
		ans = 2 ** same
	else:
		ans = 2 ** same * ncrp(diff, diff // 2, 10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))


mod = 1000000007

def multiply(pin, pop):
	return pin % mod * (pop % mod) % mod

def power(pin, pop):
	if pop == 0:
		return 1
	temp = power(pin, pop // 2)
	temp = multiply(temp, temp)
	if pop % 2:
		return multiply(temp, pin)
	return temp

def inverse(pin, m=mod):
	return power(pin, m - 2)
pl = 2 * 10 ** 5 + 1
factorial = [0 for i in range(pl)]
inverse_factorial = [0 for i in range(pl)]

def precompute():
	factorial[0] = inverse_factorial[0] = 1
	for i in range(1, pl):
		factorial[i] = multiply(factorial[i - 1], i)
		inverse_factorial[i] = multiply(inverse_factorial[i - 1], inverse(i))

def solve():
	n = int(input())
	(pl1, pl2) = (input(), input())
	count = 0
	for i in range(n):
		if pl1[i] == pl2[i]:
			count += 1
	if (n - count) % 2 == 1:
		print(0)
		return
	n -= count
	result = power(2, count)
	result = multiply(result, multiply(factorial[n], multiply(inverse_factorial[n // 2], inverse_factorial[n // 2])))
	print(result)
precompute()
number = int(input())
for i in range(number):
	solve()


MOD = 1000000007

def mul(a, b):
	return a % MOD * (b % MOD) % MOD

def binpow(a, b):
	if b == 0:
		return 1
	tmp = binpow(a, b // 2)
	tmp = mul(tmp, tmp)
	if b % 2:
		return mul(tmp, a)
	return tmp

def mod_inverse(a, m=MOD):
	return binpow(a, m - 2)
SZ = 2 * 10 ** 5 + 1
fact = [0] * SZ
invfact = [0] * SZ

def precompute():
	fact[0] = invfact[0] = 1
	for i in range(1, SZ):
		fact[i] = mul(fact[i - 1], i)
		invfact[i] = mul(invfact[i - 1], mod_inverse(i))

def solve():
	n = int(input())
	A = input()
	B = input()
	cnt = 0
	for i in range(n):
		if A[i] == B[i]:
			cnt += 1
	if (n - cnt) % 2:
		print(0)
		return
	n -= cnt
	ans = binpow(2, cnt)
	ans = mul(ans, mul(fact[n], mul(invfact[n // 2], invfact[n // 2])))
	print(ans)
precompute()
t = int(input())
for _ in range(t):
	solve()


def multiply(n1, n2):
	res = n1 % (10 ** 9 + 7) * n2 % (10 ** 9 + 7) % (10 ** 9 + 7)
	return res

def power(num1, num2):
	if num2 == 0:
		return 1
	small = power(num1, num2 // 2)
	small = multiply(small, small)
	if num2 % 2 == 1:
		ans = multiply(small, num1)
		return ans
	return small

def inv(a, m=10 ** 9 + 7):
	f = power(a, m - 2)
	return f
lis = []
inlis = []
for i in range(2 * 10 ** 5 + 1):
	lis.append(0)
	inlis.append(0)

def solve():
	lis[0] = inlis[0] = 1
	for i in range(1, len(lis)):
		lis[i] = multiply(lis[i - 1], i)
		inlis[i] = multiply(inlis[i - 1], inv(i))
solve()
for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = input()
	c = 0
	for i in range(n):
		if s[i] == s1[i]:
			c += 1
	if (n - c) % 2:
		print(0)
	else:
		n -= c
		res = power(2, c)
		d = multiply(lis[n], multiply(inlis[n // 2], inlis[n // 2]))
		res = multiply(res, d)
		print(res)


def f(m):
	num = den = 1
	for i in range(1, m // 2 + 1):
		den *= i
	for i in range(m // 2 + 1, m + 1):
		num *= i
	return num // den
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	B = input()
	n = 0
	for i in range(N):
		if A[i] == B[i]:
			n += 1
	m = N - n
	if m % 2 == 1:
		print(0)
	else:
		print(f(m) * 2 ** n % (10 ** 9 + 7))


t = int(input())
import math

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
while t > 0:
	n = int(input())
	a = str(input())
	b = str(input())
	ham_ab = 0
	for i in range(0, n):
		if a[i] != b[i]:
			ham_ab += 1
	if ham_ab % 2 == 1:
		print(0)
	else:
		pd1 = pow(2, n - ham_ab, 10 ** 9 + 7)
		pd2 = 1
		if ham_ab != 0:
			pd2 = ncr(ham_ab, int(ham_ab / 2), 10 ** 9 + 7)
		print(pd1 * pd2 % (10 ** 9 + 7))
	t -= 1


import math
MOD = 1000000007

def choose(n, k):
	k = min(k, n - k)
	result = 1
	for i in range(k):
		result = result * (n - i) % MOD
		result = result * pow(i + 1, -1, MOD) % MOD
	return result

def solve(n, a, b):
	nsame = sum((1 for (aa, bb) in zip(a, b) if aa == bb))
	ndiff = n - nsame
	if ndiff % 2 == 1:
		return 0
	return pow(2, nsame, MOD) * choose(ndiff, ndiff // 2) % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	print(solve(n, a, b))


from math import factorial as fact
for a0 in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	(pp, a, b) = (0, 0, 0)
	pp = bin(int(s1, 2) ^ int(s2, 2))[2:].count('1')
	if pp % 2:
		print(0)
		continue
	if s1 == s2:
		print(pow(2, n, 1000000007))
		continue
	ttl = fact(pp) // (fact(pp // 2) * fact(pp // 2))
	ans = pow(2, n - pp, 1000000007)
	print(ans * ttl % 1000000007)


import math

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def power(x, y, p):
	res = 1
	while y > 0:
		if y & 1 != 0:
			res = res * x
		y = y >> 1
		x = x * x
	return res % p
for aa in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	e = 1000000007
	x = 0
	y = 0
	for i in range(n):
		if a[i] == b[i]:
			x += 1
		else:
			y += 1
	if y % 2 != 0:
		print(0)
		continue
	else:
		if y == 0:
			print(int(power(2, x, e)))
			continue
		w = y // 2
		t = ncr(y, w, e)
		if x == 0:
			print(int(t) % e)
			continue
		print(int(power(2, x, e) * t) % e)