Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given two binary strings $A$ and $B$, each with length $N$. You may reorder the characters of $A$ in an arbitrary way and reorder the characters of $B$ also in an arbitrary (not necessarily the same) way. Then, you should compute the XOR of the resulting strings. Find the number of distinct values of this XOR which can be obtained, modulo $1,000,000,007$ ($10^{9} + 7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains a single string $A$ with length $N$.
The third line contains a single string $B$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer ― the number of unique XORs modulo $1,000,000,007$.

------  Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$|A| = |B| = N$
$A$ and $B$ contain only characters '0' and '1'
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (10 points):
$N ≤ 5$
the sum of $N$ over all test cases does not exceed $10$

Subtask #2 (30 points):
$N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{3}$

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------ 
1

2

00

10
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1: The characters in each string can be reordered in two ways (swap them or do nothing), so there are four values of their XOR:
- "00" XOR "10" is "10"
- "00" XOR "01" is "01"
- "00" XOR "10" is "10"
- "00" XOR "01" is "01"

There are only two distinct values.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Bit manipulation

Mathematics


Solutions:
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

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

def ncr(n, r):
	return mul(fact[n], mul(pow(fact[n - r], mod - 2, mod), pow(fact[r], mod - 2, mod)))

def answer():
	ca1 = a.count('1')
	cb1 = b.count('1')
	o = abs(ca1 - cb1)
	stop = abs(min(ca1, cb1) - min(n - ca1, n - cb1))
	ans = 0
	for i in range(n - o, stop - 1, -2):
		ans = add(ans, ncr(n, i))
	return ans
fact = [1]
for i in range(1, 10 ** 5 + 1):
	fact.append(mul(fact[-1], i))
for T in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	print(answer())


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 = x + m0
	return x
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 6 + 1):
	x = fact[-1]
	y = x * i % mod
	fact.append(y)
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(a1, b1) = (a.count('1'), b.count('1'))
	a0 = [n - a1, a1]
	b0 = [n - b1, b1]
	ma = min(n - a1, b1) + min(n - b1, a1)
	res = 0
	for i in range(ma, ma - 2 * min(min(n - a1, b1), min(n - b1, a1)) - 1, -2):
		p = n
		q = n - i
		r = i
		res += fact[p] % mod * modInverse(fact[q], mod) * modInverse(fact[r], mod)
		res = res % mod
	print(res)


f = []
f.append(1)
for z in range(1, 100001):
	f.append(z % 1000000007 * (f[z - 1] % 1000000007) % 1000000007)
T = int(input(''))
while T:
	n = int(input())
	A = input()
	B = input()
	a1 = int(A.count('1'))
	b1 = int(B.count('1'))
	c = int(0)
	m = 1000000007
	if a1 == b1:
		c = 1
	if a1 == n and b1 == 0 or (a1 == 0 and b1 == n):
		print(1)
		continue
	x = int(a1 + b1)
	if b1 <= n - a1:
		x = x
	else:
		x = 2 * n - x
	if (a1 + b1) % 2 == 0:
		for i in range(max(2, abs(a1 - b1)), x + 1, 2):
			c = c + f[n] % m * pow(f[n - i] * f[i] % 1000000007, m - 2, m) % m
			c = c % m
	else:
		for i in range(max(1, abs(a1 - b1)), x + 1, 2):
			c = c + f[n] % m * pow(f[n - i] * f[i] % 1000000007, m - 2, m) % m
			c = c % m
	print(c)
	T = T - 1


import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, combinations_with_replacement, permutations
(MAX_INT, MOD, fact, ifact) = (2 ** 62 - 1, 10 ** 9 + 7, [1] * (10 ** 6 + 1), [1] * (10 ** 6 + 1))
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
write = sys.stdout.write
for i in range(1, len(fact)):
	fact[i] = i * fact[i - 1] % MOD
ifact[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(1, len(fact) - 1)[::-1]:
	ifact[i] = ifact[i + 1] * (i + 1) % MOD

def nCr(n, i):
	return fact[n] * ifact[i] % MOD * ifact[n - i] % MOD

def solve(n, a, b):
	(a1, b1) = (a.count('1'), b.count('1'))
	(L, R, ans) = (abs(a1 - b1), n - abs(a1 + b1 - n), 0)
	for i in range(L, R + 1, 2):
		ans = (ans + nCr(n, i)) % MOD
	print(ans)
test_num = int(input())
for _ in range(test_num):
	n = int(input())
	(a, b) = (input(), input())
	solve(n, a, b)


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input().strip()
mod = 1000000007
fact = 100001 * [0]

def power(a, b, m):
	result = 1
	a = a % m
	while b > 0:
		if b & 1:
			result = (result % mod * a % mod % mod + mod) % mod
		b = b >> 1
		a = (a % mod * a % mod % mod + mod) % mod
	return int(result)

def modInverse(n, p):
	return int(power(n, p - 2, p) % mod)

def NcrModp(n, r, m):
	if r == 0 or r == n:
		return 1
	return fact[n] * (modInverse(fact[r], m) % m * modInverse(fact[n - r], m) % mod) % mod % mod
t = I()
fact[0] = 1
for i in range(1, 100001):
	fact[i] = fact[i - 1] * i % mod
for i in range(t):
	n = I()
	a = S()
	b = S()
	c = d = e = f = s = 0
	for j in range(n):
		if a[j] == '1':
			c += 1
		else:
			d += 1
		if b[j] == '1':
			e += 1
		else:
			f += 1
	mi = abs(c - e)
	ma = min(c, f) + min(d, e)
	for j in range(mi, ma + 1, 2):
		s = (s + NcrModp(n, j, mod) % mod) % mod
	print(s)


prime = 1000000007
from functools import reduce
from operator import mul

def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numerator = 1
	for i in range(n, n - r, -1):
		numerator = numerator * i % prime
	denominator = 1
	for i in range(1, r + 1):
		denominator = denominator * i % prime
	return numerator * pow(denominator, prime - 2, prime) % prime
t = int(input())
for test in range(t):
	n = int(input())
	a = input()
	b = input()
	ones_a = a.count('1')
	ones_b = b.count('1')
	if ones_a < n - ones_b:
		maxim = ones_a + ones_b
		minim = abs(ones_a - ones_b)
	else:
		maxim = 2 * n - (ones_a + ones_b)
		minim = abs(n - ones_a - (n - ones_b))
	ans = cur = ncr(n, minim)
	ans = ans % prime
	for i in range(minim + 2, maxim + 1, 2):
		cur = cur * (n - minim) % prime
		cur = cur * (n - minim - 1) % prime
		tmp = (minim + 1) * (minim + 2) % prime
		cur = cur * pow(tmp, prime - 2, prime) % prime
		ans = (ans + cur) % prime
		minim += 2
	print(ans)


pri = 10 ** 9 + 7
fact = [0 for i in range(10 ** 5 + 1)]
fact[0] = 1
fact[1] = 1
for i in range(2, len(fact)):
	fact[i] = i * (fact[i - 1] % pri) % pri
ifact = [0 for i in range(10 ** 5 + 1)]
ifact[1] = 1
ifact[0] = 1

def mod(a, y, pri):
	if y == 0:
		return 1
	else:
		p = mod(a, y // 2, pri) % pri
		p = p * p % pri
		if y % 2 == 0:
			return p
		else:
			return a * p % pri
for i in range(2, 10 ** 5 + 1):
	ifact[i] = ifact[i - 1] * mod(i, pri - 2, pri) % pri

def NcR(n, r):
	ret = ifact[n - r] * ifact[r] % pri
	ret = ret * fact[n] % pri
	return ret
p = int(input())
for i in range(p):
	opa = int(input())
	s1 = input()
	s2 = input()
	x = s1.count('1')
	y = s1.count('0')
	a = s2.count('1')
	b = s2.count('0')
	total = 0
	kap = min(x, a)
	kapa = 0
	for t in range(kap + 1):
		v = x - t
		q = b - v
		l = a - t
		if 0 <= v <= b and 0 <= q <= b and (0 <= l <= a):
			w = NcR(opa, t + q)
			e = NcR(t + q, t)
			r = NcR(v + l, v)
			kapa = kapa + w * e * r % (10 ** 9 + 7)
			kapa = (kapa - w) % (10 ** 9 + 7)
	w = NcR(opa, x)
	e = NcR(opa, a)
	zapa = w * e % (10 ** 9 + 7)
	print((zapa - kapa) % (10 ** 9 + 7))


t = int(input())
MODULO = 10 ** 9 + 7
fact = [0 for x in range(10 ** 5 + 2)]
fact[0] = 1
for i in range(1, 10 ** 5 + 2):
	fact[i] = fact[i - 1] * i % MODULO

def inverse_mult(x, pow, mod):
	a = 1
	b = x
	while pow > 0:
		if pow % 2 == 1:
			a *= b
			if a > mod:
				a %= mod
		b **= 2
		if b > mod:
			b %= mod
		pow //= 2
	return a

def nCr(n, r, m):
	return fact[n] * (inverse_mult(fact[r], m - 2, m) * inverse_mult(fact[n - r], m - 2, m)) % m % m
while t > 0:
	t -= 1
	m = int(input())
	a = input().strip()
	b = input().strip()
	a1 = sum([1 if x == '1' else 0 for x in a])
	b1 = sum([1 if x == '1' else 0 for x in b])
	max1 = min(a1, m - b1) + min(m - a1, b1)
	min1 = abs(a1 - b1)
	ans = 0
	for i in range(min1, max1 + 1, 2):
		ans += nCr(m, i, MODULO)
		ans = (ans + MODULO) % MODULO
	print(int(ans))


m = 1000000007
f = [1]
p = 1
for i in range(2, 100000):
	f.append(p)
	p = p * i % m
t = int(input())
for x in range(t):
	n = int(input())
	a = input()
	b = input()
	s = 0
	o1 = 0
	o2 = 0
	for y in range(n):
		if a[y] == '1':
			o1 = o1 + 1
		if b[y] == '1':
			o2 = o2 + 1
	st = abs(o1 - o2)
	if o1 < o2:
		o1 = o2
	en = min(o1 - st, n - o1) * 2
	en = en + st
	c = 1
	e = 0
	for y in range(st, en + 1, 2):
		b1 = int(pow(f[y], m - 2, m))
		b2 = int(pow(f[n - y], m - 2, m))
		c = f[n] * b1 * b2 % m
		s = (s + c) % m
	print(s)


from math import factorial
import math
mod = 1000000007

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:
		print('Division not defined')
	else:
		return inv * a % m
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	o1 = a.count('1')
	o2 = b.count('1')
	m = n - (o1 + o2)
	if m > 0:
		min_int = 0
	else:
		min_int = abs(m)
	max_int = min(o1, o2)
	res_max = o1 + o2 - 2 * min_int
	res_min = o1 + o2 - 2 * max_int
	fact = [1]
	f = 1
	for i in range(1, n + 1):
		f = f * i
		f = f % mod
		fact.append(f)
	c = 0
	num = fact[n]
	for i in range(res_min, res_max + 1, 2):
		c += modDivide(num, fact[i] * fact[n - i] % mod, mod)
		c = c % mod
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	aone = a.count('1')
	azero = n - aone
	bone = b.count('1')
	bzero = n - bone
	minimum = abs(aone - bone)
	maximum = min(azero, bone) + min(aone, bzero)
	mod = 1000000007
	temp = math.factorial(n) % mod * pow(math.factorial(n - minimum), mod - 2, mod) * pow(math.factorial(minimum), mod - 2, mod) % mod
	ans = temp
	for i in range(minimum + 2, maximum + 1, 2):
		temp = temp * ((n - i + 2) % mod) * ((n - i + 1) % mod) * pow(i - 1, mod - 2, mod) * pow(i, mod - 2, mod) % mod
		ans += temp
		ans %= mod
	print(ans)


from sys import stdin, stdout
fact = [1, 1]
for k in range(2, 100001):
	fact.append(k * fact[k - 1] % 1000000007)

def invMod(number):
	return pow(number, 1000000005, 1000000007)
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	str1 = stdin.readline()
	str2 = stdin.readline()
	p = 1000000007
	c0A = str1.count('0')
	c1A = n - c0A
	c0B = str2.count('0')
	c1B = n - c0B
	min1 = abs(c1A - c1B)
	max1 = min(c1A, c0B) + min(c0A, c1B)
	nf = fact[n]
	res = 0
	for i in range(min1, max1 + 1, 2):
		res = (res + nf * invMod(fact[i] * fact[n - i]) % p) % p
	print(res)


fact = [1, 1]
for k in range(2, 100001):
	fact.append(k * fact[k - 1] % 1000000007)

def invMod(number):
	return pow(number, 1000000005, 1000000007)
for _ in range(int(input())):
	n = int(input())
	str1 = input().strip()
	str2 = input().strip()
	p = 1000000007
	c0A = str1.count('0')
	c1A = n - c0A
	c0B = str2.count('0')
	c1B = n - c0B
	min1 = abs(c1A - c1B)
	max1 = min(c1A, c0B) + min(c0A, c1B)
	nf = fact[n]
	res = 0
	for i in range(min1, max1 + 1, 2):
		res = (res + nf * invMod(fact[i] * fact[n - i]) % p) % p
	print(res)


mod = 1000000007
fact = [1] * 100001
for j in range(1, 100001):
	fact[j] = fact[j - 1] * j % mod

def modInv(n, mod):
	return pow(n, mod - 2, mod)

def comb(n, x):
	return fact[n] * modInv(fact[x], mod) % mod * modInv(fact[n - x], mod) % mod % mod
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	a1 = a.count('1')
	a0 = a.count('0')
	b1 = b.count('1')
	b0 = b.count('0')
	mini = abs(a1 - b1)
	maxi = min(a0, b1) + min(b0, a1)
	ans = 0
	for i in range(mini, maxi + 1, 2):
		if i == 0 or i == n:
			ans = ans + 1
		else:
			ans = (ans + comb(n, i)) % mod
	print(ans)


import atexit
import io
import sys
from collections import defaultdict
m = 1000000007
f = [1]
p = 1
for i in range(2, 100000):
	f.append(p)
	p = p * i % m
t = int(input())
for x in range(t):
	n = int(input())
	a = input()
	b = input()
	s = 0
	o1 = 0
	o2 = 0
	for y in range(n):
		if a[y] == '1':
			o1 = o1 + 1
		if b[y] == '1':
			o2 = o2 + 1
	st = abs(o1 - o2)
	if o1 < o2:
		o1 = o2
	en = min(o1 - st, n - o1) * 2
	en = en + st
	c = 1
	e = 0
	for y in range(st, en + 1, 2):
		b1 = int(pow(f[y], m - 2, m))
		b2 = int(pow(f[n - y], m - 2, m))
		c = f[n] * b1 * b2 % m
		s = (s + c) % m
	print(s)


import math
T = int(input())
for i in range(T):
	n = int(input())
	a = list(input())
	b = list(input())
	n1 = a.count('0')
	n2 = n - n1
	n3 = b.count('0')
	n4 = n - n3
	if n1 + n3 <= n:
		diff = abs(n1 - n3)
		j = n1 + n3
	else:
		diff = abs(n2 - n4)
		j = n2 + n4
	ct = math.factorial(n) // (math.factorial(diff) * math.factorial(n - diff))
	ans = ct
	for i in range(diff + 2, j + 1, 2):
		ct = ct * (n - i + 2) * (n - i + 1) // ((i - 1) * i)
		ans = ans + ct
	print(int(ans % (10 ** 9 + 7)))


mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 5 + 10):
	fact.append(fact[i - 1] * i % mod)

def modularExponentiation(x):
	n = mod - 2
	result = 1
	while n > 0:
		if n % 2 == 1:
			result = result * x % mod
		x = x * x % mod
		n = n // 2
	return result
for _ in range(int(input())):
	n = int(input())
	a = input().count('1')
	b = input().count('1')
	min1 = abs(a - b)
	if a + b <= n:
		max1 = a + b
	else:
		max1 = 2 * n - (a + b)
	count = 0
	for i in range(min1, max1 + 1, 2):
		count += modularExponentiation(fact[n - i]) * modularExponentiation(fact[i]) % mod
	count = fact[n] % mod * count % mod
	print(int(count))


def nCk(n, k):
	result = 1
	if n - k < k:
		k = n - k
	for i in range(0, k):
		result *= n - i
		result //= i + 1
	return result
t = int(input())
for _ in range(t):
	N = int(input())
	A = input()
	B = input()
	res = 0
	countA = 0
	countB = 0
	for i in range(N):
		if A[i] == '1':
			countA += 1
		if B[i] == '1':
			countB += 1
	if countA + countB <= N:
		max1 = countA + countB
	elif countB + countA == 2 * N:
		max1 = 0
	else:
		max1 = N - (countA + countB) % N
	min1 = abs(countA - countB)
	res += nCk(N, min1)
	x = res
	while min1 < max1:
		x = (N - min1) * (N - min1 - 1) * x // ((min1 + 1) * (min1 + 2))
		res += x
		min1 += 2
	res = res % 1000000007
	print(int(res))


mod = 10 ** 9 + 7

def bicoff(n, r):
	nu = 1
	de = 1
	for i in range(r):
		nu = nu * (n - i)
		de = de * (i + 1)
	return nu // de
for t in range(int(input())):
	n = int(input())
	a1 = input().count('1')
	b1 = input().count('1')
	minbit = abs(a1 - b1)
	if a1 + b1 <= n:
		maxbit = a1 + b1
	else:
		maxbit = 2 * n - a1 - b1
	pascal = []
	pascal.append(bicoff(n, minbit))
	for i in range(minbit + 1, maxbit + 1):
		pascal.append(pascal[-1] * (n - i + 1) // i)
	sum = 0
	for i in range(0, len(pascal), 2):
		sum += pascal[i]
	print(sum % mod)


from sys import stdin
from collections import Counter
N = 100001
p = 1000000007
factorial = [None] * (N + 1)
natural = [None] * (N + 1)
fact = [None] * (N + 1)
natural[0] = natural[1] = 1
for i in range(2, N + 1, 1):
	natural[i] = natural[p % i] * (p - int(p / i)) % p
factorial[0] = factorial[1] = 1
for i in range(2, N + 1, 1):
	factorial[i] = natural[i] * factorial[i - 1] % p
fact[0] = 1
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % p
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	a = stdin.readline().strip()
	b = stdin.readline().strip()
	(c1, c2) = (Counter(a), Counter(b))
	max1 = min(c1['0'] + c2['0'], c1['1'] + c2['1'])
	min1 = abs(c2['1'] - c1['1'])
	i = max1
	ans = 0
	while i >= min1:
		ans = (ans + fact[n] * factorial[i] % p * factorial[n - i] % p) % p
		i -= 2
	print(ans)
	t -= 1


MOD = 10 ** 9 + 7
fact = [1]
for t in range(1, 10 ** 5 + 10):
	fact.append(t * fact[t - 1] % MOD)

def go(w, fact):
	for tt in range(int(input())):
		if w == 1:
			n = int(input())
			l = input()
			r = input()
		else:
			print(1 / 0)
		nFactMod = fact[n] % MOD
		l1 = l.count('1')
		r1 = r.count('1')
		min1s = max(l1, r1) - min(l1, r1)
		max1s = l1 + r1
		if l1 + r1 > n:
			max1s = 2 * n - max1s
		ans = 0
		for y in range(min1s, max1s + 1, 2):
			ans += pow(fact[n - y], MOD - 2, MOD) * pow(fact[y], MOD - 2, MOD) % MOD
		ans = nFactMod * ans % MOD
		print(int(ans))
go(1, fact)


p = 1000000007
N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
Mod = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for _ in range(int(input())):
	L = int(input())
	A = input()
	B = input()
	n1 = 0
	n2 = 0
	n3 = 0
	n4 = 0
	for x in A:
		if x == '1':
			n1 += 1
		else:
			n2 += 1
	for x in B:
		if x == '1':
			n4 += 1
		else:
			n3 += 1
	m = abs(n1 - n4)
	M = min(n1, n3) + min(n2, n4)
	sum = 0
	Rs = []
	for k in range(m, M + 1, 2):
		Rs.append(k)
	for element in Rs:
		sum = sum + Binomial(L, element, p)
	print(int(sum) % Mod)


p = 1000000007
Facts = []
Facts.append(1)
for z in range(1, 100001):
	Facts.append(z % 1000000007 * (Facts[z - 1] % 1000000007) % 1000000007)
for _ in range(int(input())):
	n = int(input())
	A = str(input())
	B = str(input())
	ones_A = A.count('1')
	ones_B = B.count('1')
	if ones_A == n and ones_B == 0 or (ones_A == 0 and ones_B == n):
		ans = 1
	else:
		ans = 0
		zeroes_A = n - ones_A
		zeroes_B = n - ones_B
		max_ones_A = max(ones_A, ones_B)
		min_zeroes_A = min(zeroes_A, zeroes_B)
		min_ones = min(ones_A, ones_B)
		if min_zeroes_A >= min_ones:
			for i in range(0, min_ones + 1):
				r = max_ones_A - i + (min_ones - i)
				ans = (ans + Facts[n] * pow(Facts[r], p - 2, p) * pow(Facts[n - r], p - 2, p) % p) % p
		else:
			temp = min_ones - min_zeroes_A
			for i in range(temp, min_ones + 1):
				r = max_ones_A - i + (min_ones - i)
				ans = (ans + Facts[n] * pow(Facts[r], p - 2, p) * pow(Facts[n - r], p - 2, p) % p) % p
	print(int(ans))


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from sys import stdin, stdout
MAXN = 100001
MOD = 1000000007
rline = lambda : stdin.readline().strip()
inverse_mul = lambda x: pow(x, MOD - 2, MOD)

def comb(n, r):
	return fact[n] * inverse_mul(fact[r] * fact[n - r]) % MOD

def solve():
	global n, a, b
	a = a.count('1')
	b = b.count('1')
	froma = abs(a - b)
	toa = min(n - a, b) + min(n - b, a)
	s = 0
	for i in range(froma, toa + 1, 2):
		s += comb(n, i)
	return s % MOD

def read_input():
	global n, a, b
	(n, a, b) = (int(rline()), rline(), rline())

def write_output(s):
	stdout.write('\n'.join(map(str, s)))

def pre_compute():
	global fact
	fact = [1] * MAXN
	for i in range(1, MAXN):
		fact[i] = fact[i - 1] * i % MOD

def main():
	pre_compute()
	s = []
	for _ in range(int(input())):
		read_input()
		answer = solve()
		s.append(answer)
	write_output(s)
main()


import numpy as np
i8 = np.int64
MOD = 1000000007

def init(fac, inv, finv):
	fac[0] = fac[1] = 1
	finv[0] = finv[1] = 1
	inv[1] = 1
	for i in range(2, fac.shape[0]):
		fac[i] = fac[i - 1] * i % MOD
		inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
		finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k, fac, finv):
	if n < k:
		return 0
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def solve_core(N, x, y, fac, finv):
	kmin = abs(x - y)
	kmax = N - abs(N - x - y)
	res = 0
	for i in range(kmin, kmax + 1, 2):
		res += com(N, i, fac, finv)
	return res % MOD

def solve(fac, finv):
	N = int(input())
	A = input()
	B = input()
	x = A.count('1')
	y = B.count('1')
	ans = solve_core(N, x, y, fac, finv)
	print(ans)

def main():
	N = 10 ** 5
	fac = np.empty(N + 1, i8)
	inv = np.empty(N + 1, i8)
	finv = np.empty(N + 1, i8)
	init(fac, inv, finv)
	T = int(input())
	for _ in range(T):
		solve(fac, finv)
main()


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	(onea, oneb) = (a.count('1'), b.count('1'))
	zeroa = n - onea
	zerob = n - oneb
	minones = abs(onea - oneb)
	if onea + oneb > n:
		maxones = zeroa + zerob
	else:
		maxones = onea + oneb
	ans = 0
	if minones == 0:
		ans = 1
		minones += 2
	num = [0] * (n + 1)
	den = [0] * (n + 1)
	c = [0] * (n + 1)
	num[0] = den[0] = c[0] = 1
	for i in range(n):
		num[i + 1] = num[i] * (n - i) % 1000000007
		den[i + 1] = den[i] * (i + 1) % 1000000007
		c[i + 1] = num[i + 1] * pow(den[i + 1], 1000000007 - 2, 1000000007) % 1000000007
	for i in range(minones, maxones + 1, 2):
		ans += c[i]
	print(int(ans % mod))


import math
p = 1000000007

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

def main():
	for i in range(int(input())):
		n = int(input())
		a = input()
		b = input()
		a1 = a.count('1') % p
		b1 = b.count('1') % p
		r = abs(a1 - b1) % p
		m = (a1 + b1) % p
		s = 0
		arr = ncr(n, n)
		if m > n:
			for i in range(r, 2 * n - m + 1, 2):
				s = (s + arr[i]) % p
		elif m == n:
			for i in range(r, n + 1, 2):
				s = (s + arr[i]) % p
		else:
			for i in range(r, m + 1, 2):
				s = (s + arr[i]) % p
		print(s % p)
main()


import math

def C(n, r):
	m = 1000000007
	n_r = int(pow(f[n - r], m - 2, m))
	r_ = int(pow(f[r], m - 2, m))
	denom = n_r * r_ % 1000000007
	num = f[n] * denom % 1000000007
	return num
p = 1
f = [1]
for u in range(2, 100000):
	f.append(p)
	p = p * u % 1000000007
t = int(input())
while t > 0:
	n = int(input())
	A = input()
	B = input()
	x = 0
	y = 0
	coun = 0
	ans = 0
	diff = 0
	for c in A:
		if c == '1':
			x = x + 1
	for c in B:
		if c == '1':
			y = y + 1
	x2 = n - x
	y2 = n - y
	if x > y:
		diff = x - y
	else:
		diff = y - x
	a1 = min(x, y)
	a2 = min(y2, x2)
	a = min(a1, a2)
	mm = diff + 2 * a
	while diff <= mm:
		ans = (ans % 1000000007 + C(n, diff) % 1000000007) % 1000000007
		diff = diff + 2
	print(ans)
	t = t - 1


p = 1000000007
fact = [1]
for i in range(1, 100001):
	fact.append(i * fact[-1] % p)

def nCr(n, r):
	if r == 0:
		return 1
	return fact[n] * pow(fact[r], p - 2, p) % p * pow(fact[n - r], p - 2, p) % p
T = int(input())
for t in range(T):
	n = int(input())
	(b1, b2) = (input(), input())
	(c1, c2) = (sum((1 for c in b1 if c == '1')), sum((1 for c in b2 if c == '1')))
	low = abs(c2 - c1)
	high = n - abs(c1 + c2 - n)
	res = 0
	for i in range(low, high + 1, 2):
		res = (res + nCr(n, i)) % p
	print(res)


import operator as op
from functools import reduce

def nCr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = input()
	b = input()
	a1 = a.count('1')
	a0 = a.count('0')
	b1 = b.count('1')
	b0 = b.count('0')
	begin = n - min(a1, b1) - min(a0, b0)
	end = min(a0, b1) + min(a1, b0)
	if begin == end:
		print(nCr(n, begin) % 1000000007)
	else:
		lst = [nCr(n, begin)]
		for m in range(2, end - begin + 1, 2):
			lst.append(lst[-1] * ((n - begin - m + 1) * (n - begin - m + 2)) // ((begin + m - 1) * (begin + m)))
		print(sum(lst) % 1000000007)


def ncr(n, min1, max1, p):
	res = 0
	num = 1
	den = 1
	if min1 == 0:
		res = 1
	for i in range(max1):
		num = num * (n - i) % p
		den = den * (i + 1) % p
		if i - min1 >= -1 and (i - min1 + 1) % 2 == 0:
			res = (res + num * pow(den, p - 2, p)) % p
	return res
t = int(input())
p = 10 ** 9 + 7
while t > 0:
	t -= 1
	n = int(input())
	a = input().strip()
	b = input().strip()
	a_1 = 0
	b_1 = 0
	for i in a:
		if i == '1':
			a_1 += 1
	for i in b:
		if i == '1':
			b_1 += 1
	max1 = n - abs(n - (a_1 + b_1))
	min1 = max(a_1, b_1) - min(a_1, b_1)
	print(ncr(n, min1, max1, p))


def ncr(n, min1, max1, p):
	res = 0
	num = 1
	den = 1
	if min1 == 0:
		res = 1
	for i in range(max1):
		num = num * (n - i) % p
		den = den * (i + 1) % p
		if i - min1 >= -1 and (i - min1 + 1) % 2 == 0:
			res = (res + num * pow(den, p - 2, p)) % p
	return res
t = int(input())
p = 10 ** 9 + 7
while t > 0:
	t -= 1
	n = int(input())
	a = input().strip()
	b = input().strip()
	c0A = c1A = c0B = c1B = 0
	for c in a:
		if c == '1':
			c1A += 1
		elif c == '0':
			c0A += 1
	for c in b:
		if c == '1':
			c1B += 1
		elif c == '0':
			c0B += 1
	max1 = min(c0A, c1B) + min(c1A, c0B)
	min1 = n - min(c0B, c0A) - min(c1A, c1B)
	print(ncr(n, min1, max1, p))


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for t in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c1 = a.count('0')
	c2 = n - c1
	c3 = b.count('0')
	c4 = n - c3
	end = min(c1, c4) + min(c2, c3)
	begin = n - (min(c1, c3) + min(c2, c4))
	if begin == end:
		print(ncr(n, begin) % 1000000007)
	else:
		lst = [ncr(n, begin)]
		for m in range(2, end - begin + 1, 2):
			lst.append(lst[-1] * ((n - begin - m + 1) * (n - begin - m + 2)) // ((begin + m - 1) * (begin + m)))
		print(sum(lst) % 1000000007)


N = 100001
p = 1000000007
factorial = [None] * (N + 1)
natural = [None] * (N + 1)
fact = [None] * (N + 1)
natural[0] = natural[1] = 1
for i in range(2, N + 1, 1):
	natural[i] = natural[p % i] * (p - int(p / i)) % p
factorial[0] = factorial[1] = 1
for i in range(2, N + 1, 1):
	factorial[i] = natural[i] * factorial[i - 1] % p
fact[0] = 1
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % p
for _ in range(int(input())):
	n = int(input())
	p = 1000000007
	a = input()
	b = input()
	a1 = a.count('1')
	a0 = n - a1
	b0 = b.count('0')
	b1 = n - b0
	ans = 0
	start = n - min(a1, b1) - min(a0, b0)
	end = min(a0, b1) + min(a1, b0)
	for i in range(start, end + 1, 2):
		ans = (ans + fact[n] * factorial[i] % p * factorial[n - i] % p) % p
	print(ans)


def ppp(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def modIn(abca, M):
	return ppp(abca, M - 2, M)
try:
	t = int(input())
	l = [1, 1]
	e = 10 ** 9 + 7
	for i in range(2, 100001):
		l.append(i % e * l[i - 1] % e % e)
	for jj in range(t):
		n = int(input())
		a = input()
		b = input()
		ac = a.count('1')
		bc = b.count('1')
		count = 0
		c = abs(ac - bc)
		x = ac + bc
		if x > n:
			x = n - (x - n)
		while c <= x:
			inv = modIn(l[n - c] * l[c], e)
			ncr = l[n] % e * (inv % e) % e
			count = (count + ncr) % e
			c += 2
		print(count)
except:
	pass


fac = []

def fact(n):
	if n == 0:
		return 1
	else:
		return n * fact(n - 1)

def nCrModp(n, r, p):
	C = [0 for i in range(r + 1)]
	C[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, r), 0, -1):
			C[j] = (C[j] + C[j - 1]) % p
	return C[r]

def ncr(n, r1, r2, p):
	num = den = 1
	sum = 0
	if r1 == 0:
		sum += 1
	for i in range(r2):
		num = num * (n - i) % p
		den = den * (i + 1) % p
		if i - r1 >= -1 and (i - r1 + 1) % 2 == 0:
			sum += num * pow(den, p - 2, p) % p
			sum %= p
	return sum
for _ in range(int(input())):
	N = int(input())
	A = input()
	B = input()
	c0A = c1A = c0B = c1B = 0
	for c in A:
		if c == '1':
			c1A += 1
		elif c == '0':
			c0A += 1
	for c in B:
		if c == '1':
			c1B += 1
		elif c == '0':
			c0B += 1
	max1xor = min(c0A, c1B) + min(c1A, c0B)
	min1xor = N - min(c0B, c0A) - min(c1A, c1B)
	pdt = ncr(N, min1xor, max1xor, 10 ** 9 + 7)
	print(pdt)


M = 1000000007
fact = [0] * 2000001
fact[0] = 1
for i in range(1, 2000001):
	fact[i] = fact[i - 1] % M * (i % M) % M

def ncr(List, N):
	Summation = 0
	for i in List:
		Summation += fact[N] * pow(fact[i], M - 2, M) * pow(fact[N - i], M - 2, M) % M
	return Summation % M
for _ in range(int(input())):
	N = int(input())
	X = input()
	Y = input()
	A = X.count('1')
	B = Y.count('1')
	if A + B > N:
		Max = N - A + (N - B)
	else:
		Max = A + B
	Min = abs(A - B)
	List = []
	for i in range(Min, Max + 1, 2):
		List.append(i)
	print(ncr(List, N))


def inverse(a, p):
	if p == 0:
		return 1
	x = inverse(a, p // 2) % 1000000007
	x = x * x % 1000000007
	if p % 2 == 0:
		return x
	else:
		return a * x % 1000000007
mod = 1000000007
inv = [1, 1]
for i in range(2, 10 ** 5 + 1):
	inv.append(inverse(i, mod - 2))
fact_inv = [1, 1]
temp = 1
for i in range(2, 10 ** 5 + 1):
	temp = temp * inv[i] % mod
	fact_inv.append(temp)
facts = [1]
for i in range(1, 10 ** 5 + 1):
	facts.append(facts[i - 1] * i % (10 ** 9 + 7))
for _ in range(int(input())):
	n = int(input())
	x = input()
	y = input()
	y0 = y.count('0')
	y1 = n - y0
	x0 = x.count('0')
	x1 = n - x0
	maxx = x1 + y1
	if maxx > n:
		maxx = 2 * n - maxx
	factn = facts[n]
	minn = abs(x1 - y1)
	ans = 0
	for i in range(minn, maxx + 1, 2):
		x = factn
		v = fact_inv[i] * fact_inv[n - i]
		v = v % 1000000007
		x = x * v
		x = x % 1000000007
		ans = ans + x
		ans = ans % 1000000007
	print(ans)


import math

def solve1(x, y, mod):
	res = 1
	x = x % mod
	num = 5
	ar = []
	for i in range(num):
		ar.append(i)
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res

def solve2(numm, mod):
	return solve1(numm, mod - 2, mod)

def solve3(facatnum, numm, r, mod):
	if r == 0:
		return 1
	return facatnum[numm] * solve2(facatnum[r], mod) % mod * solve2(facatnum[numm - r], mod) % mod % mod
mod = 10 ** 9 + 7
test = int(input())
for intr in range(test):
	numm = int(input())
	arr1 = list(map(int, input().strip()))
	arr2 = list(map(int, input().strip()))
	counta1 = 0
	countb1 = 0
	counta2 = 0
	countb2 = 0
	for i in range(numm):
		if arr1[i] == 1:
			counta1 += 1
		if arr2[i] == 1:
			countb1 += 1
		if arr1[i] == 0:
			counta2 += 1
		if arr2[i] == 0:
			countb2 += 1
	valueR = abs(counta1 - countb1)
	MAXI = min(counta1 + countb1, counta2 + countb2)
	actualans = 0
	facatnum = [1]
	for i in range(1, numm + 1):
		facatnum.append(0)
	for i in range(1, numm + 1):
		facatnum[i] = facatnum[i - 1] * i % mod
	flag = 0
	while valueR <= MAXI:
		actualans = (actualans + solve3(facatnum, numm, valueR, mod)) % mod
		valueR += 2
		flag += 1
	print(actualans % mod)


fact = []
N = 10 ** 5 + 1
fact.append(1)
mod = 10 ** 9 + 7
for i in range(1, N):
	fact.append(fact[i - 1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	x1 = a.count('1')
	x0 = n - x1
	y1 = b.count('1')
	y0 = n - y1
	if x1 == 0 or x0 == 0:
		qq = fact[n]
		c1 = y1
		i1 = int(pow(fact[n - c1], mod - 2, mod))
		i2 = int(pow(fact[c1], mod - 2, mod))
		qq = qq * i1 * i2 % mod
		print(qq)
		continue
	if y1 == 0 or y0 == 0:
		qq = fact[n]
		c1 = x1
		i1 = int(pow(fact[n - c1], mod - 2, mod))
		i2 = int(pow(fact[c1], mod - 2, mod))
		qq = qq * i1 * i2 % mod
		print(qq)
		continue
	a = x1 * '1'
	a = a + x0 * '0'
	b = y0 * '0'
	b += '1' * y1
	(c1, c0) = (0, 0)
	for i in range(n):
		if a[i] != b[i]:
			c1 += 1
		else:
			c0 += 1
	d = max(x1, y1) - min(x1, y1)
	res = 0
	while c1 >= d:
		qq = fact[n]
		i1 = int(pow(fact[n - c1], mod - 2, mod))
		i2 = int(pow(fact[c1], mod - 2, mod))
		qq = qq * i1 * i2 % mod
		c1 -= 2
		c0 += 2
		res = (res + qq) % mod
	print(res)


def nCr(n, i):
	if i > n - i:
		i = n - i
	res = 1
	for k in range(i):
		res = res * (n - k)
		res = res // (k + 1)
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	b = input()
	count1 = a.count('1')
	count2 = b.count('1')
	if count1 > count2:
		mini = count1 - count2
	else:
		mini = count2 - count1
	if count1 + count2 <= n:
		maxi = count1 + count2
	else:
		maxi = 2 * n - (count1 + count2)
	i = mini
	if i > n - i:
		i = n - i
	count = 1
	for x in range(i):
		count = count * (n - x)
		count = count // (x + 1)
	count = int(count)
	temp = count
	i = mini + 2
	while i <= maxi:
		temp = temp * (n - i + 2) * (n - i + 1)
		temp = temp // i
		temp = temp // (i - 1)
		count = count + temp
		i += 2
	count = int(count)
	count = count % 1000000007
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	str1 = input()
	str2 = input()
	(n1, n2) = (0, 0)
	for i in range(n):
		if str1[i] == '1':
			n1 += 1
		if str2[i] == '1':
			n2 += 1
	ones = abs(n2 - n1)
	x = min(min(n1, n2), n - max(n1, n2))
	tot = 0
	perm = 1
	if ones == 0:
		if x > 0:
			ones = 2
			x -= 1
		tot = 1
	for i in range(1, ones + 1):
		perm = perm * (n + 1 - i) // i
		if i == ones:
			tot += perm
	for i in range(ones + 2, ones + x * 2 + 1, 2):
		perm = perm * (n - i + 2) // (i - 1)
		perm = perm * (n - i + 1) // i
		tot += perm
	print(tot % 1000000007)


mod = 1000000007

def findgcd(a, b, i, j):
	if a == 0:
		i = 0
		j = 1
		return [b, i, j]
	else:
		i1 = 0
		j1 = 0
		l = findgcd(b % a, a, i1, j1)
		(gcd, i1, j1) = (l[0], l[1], l[2])
		i = j1 - b // a * i1
		j = i1
		return [gcd, i, j]

def go3(a, n):
	i = 0
	j = 0
	l = findgcd(a, n, i, j)
	(gcd, i, j) = (l[0], l[1], l[2])
	if gcd != 1:
		return -1
	else:
		return (i % n + n) % n

def go2(a, b):
	a %= mod
	i = go3(b, mod)
	if i == -1:
		return -1
	else:
		return i * a % mod

def go(a, b, n):
	a0 = 0
	b0 = 0
	a1 = 0
	b1 = 0
	for i in range(0, n):
		if a[i] == '0':
			a0 += 1
		else:
			a1 += 1
	for i in range(0, n):
		if b[i] == '0':
			b0 += 1
		else:
			b1 += 1
	minones = n - (min(a0, b0) + min(a1, b1))
	maxones = min(a1, b0) + min(a0, b1)
	ans = 0
	itr = 1
	no = 1
	d = 1
	for i in range(minones, maxones + 1, 2):
		if i == minones:
			for j in range(0, i):
				no = no * (n - j) % mod
				d = d * (j + 1) % mod
			ans = go2(no, d) % mod
			itr = ans
		else:
			no = no * (n - i + 1) % mod
			no = no * (n - i + 2) % mod
			d = d * i % mod
			d = d * (i - 1) % mod
			itr = itr * (n - i + 1) % mod
			itr = itr * (n - i + 2) % mod
			itr = go2(itr, i) % mod
			itr = go2(itr, i - 1) % mod
			ans = (ans + go2(no, d)) % mod
	return ans
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = input()
	b = input()
	print(go(a, b, n))


t = int(input())

def fact(n):
	if n == 0 or n == 1:
		return 1
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i
	return ans

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

def find(n, max_0, min_1, max_1, min_0):
	(num, den) = ncr(n, min_1)
	p = 10 ** 9 + 7
	add = num * pow(den, p - 2, p) % p
	ans = add
	for x in range(min_1 + 2, max_1 + 1, 2):
		num = num * (n - (x - 2)) % p * (n - (x - 1)) % p
		den = den * (x - 1) % p * x % p
		add = num * pow(den, p - 2, p) % p
		ans += add
	return ans
for loop in range(t):
	n = int(input())
	a = input()
	b = input()
	x1 = 0
	y1 = 0
	x2 = 0
	y2 = 0
	for c in a:
		if c == '1':
			x1 += 1
		else:
			y1 += 1
	for c in b:
		if c == '1':
			x2 += 1
		else:
			y2 += 1
	max_1 = min(x1, y2) + min(x2, y1)
	max_0 = min(x1, x2) + min(y2, y1)
	min_0 = n - max_1
	min_1 = n - max_0
	ans = find(n, max_0, min_1, max_1, min_0)
	print(int(ans) % (10 ** 9 + 7))


import itertools
import math

def gcd(c, d):
	(reml, rem) = (abs(c), abs(d))
	(x, xl, y, yl) = (0, 1, 1, 0)
	while rem:
		(reml, (q, rem)) = (rem, divmod(reml, rem))
		(x, xl) = (xl - q * x, x)
		(y, yl) = (yl - q * y, y)
	return (reml, xl * (-1 if c < 0 else 1), yl * (-1 if d < 0 else 1))

def modinv(a, m):
	(g, x, y) = gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a1 = a.count('1')
	a0 = a.count('0')
	b1 = b.count('1')
	b0 = b.count('0')
	mi = n - (min(a1, b1) + min(a0, b0))
	ma = min(a1, b0) + min(a0, b1)
	fac = math.factorial(n)
	count = 0
	li = []
	for j in range(mi, ma + 1, 2):
		li.append(min(j, n - j))
	li.sort()
	a1 = li[0]
	x1 = math.factorial(n) // (math.factorial(a1) * math.factorial(n - a1))
	result = x1 % (10 ** 9 + 7)
	for i in range(1, len(li)):
		if li[i] - li[i - 1] == 1:
			x1 = x1 * ((n - li[i] + 1) % (10 ** 9 + 7)) % (10 ** 9 + 7) * modinv(li[i], 10 ** 9 + 7) % (10 ** 9 + 7)
		elif li[i] - li[i - 1] == 2:
			x1 = x1 * ((n - li[i] + 2) % (10 ** 9 + 7)) % (10 ** 9 + 7) * modinv(li[i] - 1, 10 ** 9 + 7) % (10 ** 9 + 7)
			x1 = x1 * ((n - li[i] + 1) % (10 ** 9 + 7)) % (10 ** 9 + 7) * modinv(li[i], 10 ** 9 + 7) % (10 ** 9 + 7)
		result += x1
		result %= 10 ** 9 + 7
	print(result)


s = [0] * 100001
s[0] = 1
m = 1000000007
for i in range(1, 100001):
	s[i] = s[i - 1] * i % m
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	a1 = a.count('1')
	b1 = b.count('1')
	az = a.count('0')
	bz = b.count('0')
	mini = abs(a1 - b1)
	maxi = a1 + b1
	if maxi > n:
		if az < bz:
			maxi = n - (b1 - az)
		else:
			maxi = n - (a1 - bz)
	ans = 0
	for j in range(mini, maxi + 1, 2):
		b = pow(s[j] * s[n - j], m - 2, m)
		ans = (ans + s[n] % m * b % m) % m
	print(ans)


p = 1000000007
fac = [0] * 150001
fac[0] = 1
for i in range(1, 150001):
	fac[i] = fac[i - 1] * i % p
t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	a = input()
	b = input()
	c1 = a.count('1')
	c2 = b.count('1')
	if n < c1 + c2:
		Max = 2 * n - c1 - c2
	else:
		Max = c1 + c2
	Min = abs(c1 - c2)
	for j in range(Min, Max + 1, 2):
		ans += fac[n] * pow(fac[j], p - 2, p) * pow(fac[n - j], p - 2, p) % p
		ans = ans % p
	print(ans)


def comb(n, k):
	if k > n - k:
		k = n - k
	val = 1
	for i in range(k):
		val = val * (n - i)
		val = val // (i + 1)
	return val
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = input()
	b = input()
	a1 = a.count('1')
	b1 = b.count('1')
	one_diff = abs(a1 - b1)
	if a1 + b1 <= n:
		bloo = a1 + b1
	else:
		bla = a1 + b1 - n
		bloo = a1 + b1 - 2 * bla
	count = comb(n, one_diff)
	ans = count
	for i in range(one_diff + 2, bloo + 1, 2):
		count = count * ((n - i + 1) * (n - i + 2)) // ((i - 1) * i)
		ans += count
	print(ans % 1000000007)


fact = [1] * 10 ** 6
mod = 10 ** 9 + 7
for i in range(1, 10 ** 6):
	fact[i] = fact[i - 1] * i % mod
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	no1 = min(s1.count('1'), s2.count('0')) + min(s1.count('0'), s2.count('1'))
	nfact = fact[n]
	st = no1
	ans = 0
	st = abs(s1.count('1') - s2.count('1'))
	while st <= no1:
		ans += nfact * pow(fact[st], mod - 2, mod) * pow(fact[n - st], mod - 2, mod) % mod
		ans = ans % mod
		st += 2
	print(ans)


import math as mat
test = int(input())
while test != 0:
	test = test - 1
	n = int(input())
	a = input()
	b = input()
	ca = 0
	cb = 0
	sum = 0
	temp = 1
	temp1 = 1
	for i in range(0, n):
		if a[i] == '1':
			ca = ca + 1
		if b[i] == '1':
			cb = cb + 1
	if ca + cb > n:
		max = 2 * n - (ca + cb)
		min = abs(ca - cb)
		for i in range(min, max + 1, 2):
			if i == min:
				for j in range(i):
					temp = temp * (n - j) % 1000000007
					temp1 = temp1 * (j + 1) % 1000000007
			else:
				for j in range(i - 2, i):
					temp = temp * (n - j) % 1000000007
					temp1 = temp1 * (j + 1) % 1000000007
			sum = (sum % 1000000007 + temp % 1000000007 * (pow(temp1, 1000000005, 1000000007) % 1000000007) % 1000000007) % 1000000007
		print(int(sum % 1000000007))
	else:
		max = ca + cb
		min = abs(ca - cb)
		for i in range(min, max + 1, 2):
			if i == min:
				for j in range(i):
					temp = temp * (n - j) % 1000000007
					temp1 = temp1 * (j + 1) % 1000000007
			else:
				for j in range(i - 2, i):
					temp = temp * (n - j) % 1000000007
					temp1 = temp1 * (j + 1) % 1000000007
			sum = (sum % 1000000007 + temp % 1000000007 * (pow(temp1, 1000000005, 1000000007) % 1000000007) % 1000000007) % 1000000007
		print(int(sum % 1000000007))


N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
T = int(input())
for Z in range(T):
	n = int(input())
	x = input()
	y = input()
	a = x.count('1')
	b = y.count('1')
	if a + b <= n:
		maximum = a + b
	elif a + b > n:
		maximum = n - (a + b - n)
	minimum = max(a, b) - min(a, b)
	sum = 0
	for i in range(minimum, maximum + 1, 2):
		sum = (sum + int(Binomial(n, i, p))) % (10 ** 9 + 7)
	print(sum)


import math

def nCr(n, r, m):
	res = fact[n] % m * pow(fact[r], m - 2, m) % m % m
	res = res % m * pow(fact[n - r], m - 2, m) % m % m
	return res
fact = [1]
mul = 1
m = 1000000007
for i in range(1, 100002):
	mul = mul % m * (i % m) % m
	fact.append(mul)
t = int(input())
for q in range(t):
	n = int(input())
	a = input()
	b = input()
	n1 = a.count('1')
	n2 = b.count('1')
	if n1 == n:
		n1 = 0
	if n2 == n:
		n2 = 0
	if n1 > math.floor(n / 2):
		n1 = n // 2 - n1 % math.ceil(n / 2)
	if n2 > math.floor(n / 2):
		n2 = n // 2 - n2 % math.ceil(n / 2)
	e = n1 + n2
	res = 0
	while e >= 0 and min(n2, n1) >= 0:
		res = (res % m + nCr(n, e, m) % m) % m
		e = e - 2
		n1 = n1 - 1
		n2 = n2 - 1
	print(res)


import itertools
import math

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, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	a = list(a)
	b = list(b)
	a1 = a.count('1')
	a0 = a.count('0')
	b1 = b.count('1')
	b0 = b.count('0')
	min1 = n - (min(a1, b1) + min(a0, b0))
	max1 = min(a1, b0) + min(a0, b1)
	nfac = math.factorial(n)
	c = 0
	list1 = []
	for j in range(min1, max1 + 1, 2):
		list1.append(min(j, n - j))
	list1.sort()
	a1 = list1[0]
	x1 = math.factorial(n) // (math.factorial(a1) * math.factorial(n - a1))
	ans = x1 % 1000000007
	for i in range(1, len(list1)):
		if list1[i] - list1[i - 1] == 1:
			x1 = x1 * ((n - list1[i] + 1) % 1000000007) % 1000000007 * modinv(list1[i], 1000000007) % 1000000007
		elif list1[i] - list1[i - 1] == 2:
			x1 = x1 * ((n - list1[i] + 2) % 1000000007) % 1000000007 * modinv(list1[i] - 1, 1000000007) % 1000000007
			x1 = x1 * ((n - list1[i] + 1) % 1000000007) % 1000000007 * modinv(list1[i], 1000000007) % 1000000007
		ans += x1
		ans %= 1000000007
	print(ans)


import math
MM = 1000000007
fact = []
fact.append(1)
for i in range(1, 1000001):
	fact.append(fact[i - 1] * i % 1000000007)
for _ in range(int(input())):
	x = int(input())
	n = list(input())
	m = list(input())
	count1 = 0
	count2 = 0
	for i in n:
		if i == '1':
			count1 += 1
	for i in m:
		if i == '1':
			count2 += 1
	lf = fact[x]
	countz1 = x - count1
	countz2 = x - count2
	ways = 0
	if countz1 < countz2:
		for _ in range(countz1 + 1):
			if count2 < 0:
				break
			c1 = count1 - count2
			mmi = fact[c1] * fact[x - c1]
			wd = pow(mmi, MM - 2, MM) * (lf % MM) % MM
			ways += wd
			count1 += 1
			count2 -= 1
	else:
		for _ in range(countz2 + 1):
			if count1 < 0:
				break
			c1 = count2 - count1
			mmi = fact[c1] * fact[x - c1]
			wd = pow(mmi, MM - 2, MM) * (lf % MM) % MM
			ways += wd
			count2 += 1
			count1 -= 1
	print(ways % 1000000007)


l = [1]
s = pow(10, 9) + 7
k = pow(10, 5)
for i in range(1, k + 1):
	l.append(l[-1] * i % s)
mod = [1]
for i in range(1, k + 1):
	mod.append(pow(l[i], s - 2, s))
t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	a = 0
	b = 0
	c = 0
	d = 0
	for k in range(len(s1)):
		if s1[k] == '0' and s2[k] == '0':
			d += 1
		elif s1[k] == '1' and s2[k] == '0':
			a += 1
		elif s1[k] == '0' and s2[k] == '1':
			b += 1
		else:
			c += 1
	max_0 = c + d + 2 * min(a, b)
	max_1 = a + b + 2 * min(c, d)
	min_1 = n - max_0
	ans = 0
	for z in range(min_1, max_1 + 1, 2):
		ans += l[n] * mod[z] * mod[n - z] % s
		ans = ans % s
	print(ans)


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:
		x = 4 // 0
	else:
		return inv * a % m
fc2 = [1, 1]
for i in range(2, 100000 + 2):
	fc2.append(fc2[i - 1] * i % (10 ** 9 + 7))
t = int(input())
for test in range(t):
	n = int(input())
	a = input()
	b = input()
	A = {'1': 0, '0': 0}
	B = {'1': 0, '0': 0}
	for i in range(n):
		A[a[i]] += 1
		B[b[i]] += 1
	max_1 = min(A['0'], B['1']) + min(A['1'], B['0'])
	min_1 = n - (min(A['0'], B['0']) + min(A['1'], B['1']))
	num = 0
	for x in range(max_1, min_1 - 1, -2):
		a = fc2[n]
		b = fc2[x] * fc2[n - x]
		num += modDivide(a, b, 10 ** 9 + 7)
		num = num % (10 ** 9 + 7)
	print(num)


import math
test = int(input())
n = 1000000
t = 1
factorial = [1]
MOD = 10 ** 9 + 7
for x in range(1, n + 1):
	t = t * x % MOD
	factorial.append(t)

def solve():
	coll = 0
	n = int(input())
	num_A = input()
	num_B = input()
	ones_A = num_A.count('1')
	ones_B = num_B.count('1')
	add = ones_A + ones_B
	subs = abs(ones_A - ones_B)
	if n >= add:
		for x in range(subs, add + 1, 2):
			coll = (coll + nCr(n, x)) % MOD
	else:
		for x in range(subs, 2 * n - add + 1, 2):
			coll = (coll + nCr(n, x)) % MOD
	print(coll)

def InverseMod(num):
	return pow(num, MOD - 2, MOD)

def nCr(n, r):
	return factorial[n] * InverseMod(factorial[r] * factorial[n - r] % MOD)
for x in range(test):
	solve()


fact = []
fact.append(1)
for j in range(1, 100001):
	fact.append(j % 1000000007 * (fact[j - 1] % 1000000007) % 1000000007)
T = int(input())
while T:
	n = int(input())
	a = input()
	b = input()
	a1 = int(a.count('1'))
	b1 = int(b.count('1'))
	k = int(0)
	m = 1000000007
	if a1 == b1:
		k = 1
	if a1 == n and b1 == 0 or (a1 == 0 and b1 == n):
		print(1)
		continue
	x = int(a1 + b1)
	if b1 <= n - a1:
		x = x
	else:
		x = 2 * n - x
	if (a1 + b1) % 2 == 0:
		for i in range(max(2, abs(a1 - b1)), x + 1, 2):
			k = k + fact[n] % m * pow(fact[n - i] * fact[i] % 1000000007, m - 2, m) % m
			k = k % m
	else:
		for i in range(max(1, abs(a1 - b1)), x + 1, 2):
			k = k + fact[n] % m * pow(fact[n - i] * fact[i] % 1000000007, m - 2, m) % m
			k = k % m
	print(k)
	T = T - 1


def cones(s):
	o = 0
	for i in s:
		if i == '1':
			o += 1
	return o

def pul(a, b, c):
	a1 = 1
	b1 = a
	while b > 0:
		if b % 2 == 1:
			a1 = a1 * b1
			if a1 > c:
				a1 = a1 % c
		b1 = b1 ** 2
		if b1 > c:
			b1 = b1 % c
		b = b // 2
	return a1

def nCr(n, t, m):
	return f[n] * (pul(f[t], m - 2, m) * pul(f[n - t], m - 2, m) % m) % m
f = [0 for x in range(100004)]
f[0] = 1
for i in range(1, 100002):
	f[i] = f[i - 1] * i % 1000000007
test = int(input())
while test > 0:
	test -= 1
	res = 0
	n = int(input())
	a = input()
	b = input()
	coua = cones(a)
	coub = cones(b)
	t = coua + coub
	if coua == coub:
		res = 1
	while t >= abs(coua - coub):
		if t == n:
			if t == coua + coub:
				res = (res + nCr(n, t, 1000000007)) % 1000000007
		if t < n:
			if t > 0 and t <= 2 * n - coua - coub:
				res = (res + nCr(n, t, 1000000007)) % 1000000007
		t -= 2
	print(res % 1000000007)


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 onesList(a, b, n):
	maxi = max(a, b)
	mini = min(a, b)
	p = 2 * n - (a + b)
	if a + b <= n:
		return list(range(maxi - mini, maxi + mini + 1, 2))
	else:
		return list(range(maxi - mini, p + 1, 2))

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p
try:
	N = 1000001
	factorialNumInverse = [None] * (N + 1)
	naturalNumInverse = [None] * (N + 1)
	fact = [None] * (N + 1)
	p = 1000000007
	InverseofNumber(p)
	InverseofFactorial(p)
	factorial(p)
	t = int(input())
	for i in range(t):
		n = int(input())
		a = input()
		b = input()
		l = onesList(a.count('1'), b.count('1'), n)
		ans = 0
		for i in l:
			ans += Binomial(n, i, 1000000007) % 1000000007
		print(ans % 1000000007)
except:
	pass


P = 1000000007
factorialNumInverse = [None] * (100000 + 2)
naturalNumInverse = [None] * (100000 + 2)
fact = [None] * (100000 + 2)

def InverseofNumber():
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, 100000 + 2, 1):
		naturalNumInverse[i] = naturalNumInverse[P % i] * (P - int(P / i)) % P

def InverseofFactorial():
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, 100000 + 2, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % P

def factorial():
	fact[0] = 1
	for i in range(1, 100000 + 2):
		fact[i] = fact[i - 1] * i % P

def Binomial(n, R):
	ans = fact[n] * factorialNumInverse[R] % P * factorialNumInverse[n - R] % P
	return ans
InverseofNumber()
InverseofFactorial()
factorial()
t = int(input())
for _ in range(t):
	n = int(input())
	A = input()
	B = input()
	n1a = 0
	n0a = 0
	n1b = 0
	n0b = 0
	for i in A:
		if i == '0':
			n0a += 1
	n1a = n - n0a
	for i in B:
		if i == '0':
			n0b += 1
	n1b = n - n0b
	max_1 = min(n1a, n0b) + min(n0a, n1b)
	min_1 = n - (min(n1a, n1b) + min(n0a, n0b))
	sum1 = 0
	while max_1 >= min_1:
		sum1 += Binomial(n, max_1)
		sum1 = sum1 % P
		max_1 = max_1 - 2
	print(sum1)


N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * 100001

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
tc = int(input())
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
fact[0] = 1
for i in range(1, 100000 + 1):
	fact[i] = fact[i - 1] * i % p
for x in range(tc):
	n = int(input())
	mod = 1000000007
	a = input()
	b = input()
	a0 = a.count('0')
	a1 = a.count('1')
	b0 = b.count('0')
	b1 = b.count('1')
	mi = abs(a1 - b1)
	s = 0
	ma = min(a0, b1) + min(a1, b0)
	anss = 0
	for i in range(mi, ma + 1, 2):
		s += Binomial(n, i, mod)
	print(s % mod)


mod = pow(10, 9) + 7
f = [1]
p = 1
for x in range(2, 100001):
	f.append(p)
	p = p * x % mod
for x in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c00 = 0
	c01 = 0
	c10 = 0
	c11 = 0
	sum1 = 0
	for x1 in a:
		if x1 == '0':
			c00 += 1
		else:
			c01 += 1
	for x1 in b:
		if x1 == '0':
			c10 += 1
		else:
			c11 += 1
	m0 = min(c00, c10)
	m1 = min(c01, c11)
	r = n - m0 - m1
	t = f[n] % mod
	for x in range(r, r + m0 * 2 + 1, 2):
		if x <= c01 + c11:
			y = int(pow(f[n - x], mod - 2, mod))
			y1 = int(pow(f[x], mod - 2, mod))
			d = y * y1 % mod
			sum1 = (sum1 + t * d) % mod
	print(sum1)


from sys import stdin, stdout
from math import gcd
try:
	N = 1000001
	factorialNumInverse = [None] * (N + 1)
	naturalNumInverse = [None] * (N + 1)
	fact = [None] * (N + 1)

	def InverseofNumber(p):
		naturalNumInverse[0] = naturalNumInverse[1] = 1
		for i in range(2, N + 1, 1):
			naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

	def InverseofFactorial(p):
		factorialNumInverse[0] = factorialNumInverse[1] = 1
		for i in range(2, N + 1, 1):
			factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

	def factorial(p):
		fact[0] = 1
		for i in range(1, N + 1):
			fact[i] = fact[i - 1] * i % p

	def Binomial(N, R, p):
		ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
		return ans
	p = 1000000007
	InverseofNumber(p)
	InverseofFactorial(p)
	factorial(p)
	k1 = int(input())
	for _ in range(k1):
		k = int(input())
		a = input()
		b = input()
		c1 = 0
		c1o = 0
		c2 = 0
		c2o = 0
		for i in a:
			if i == '1':
				c1 += 1
			else:
				c1o += 1
		for i in b:
			if i == '1':
				c2 += 1
			else:
				c2o += 1
		max_bits = min(c2o, c1) + min(c2, c1o)
		min_bits = abs(c2 - c1)
		r = max_bits
		Sum = 0
		while r >= min_bits:
			Sum += Binomial(k, r, p) % p
			r -= 2
		print(Sum % p)
except:
	pass


def ncr(n, mini, maxi):
	p = 1000000007
	num = 1
	den = 1
	for i in range(mini):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	final = num * pow(den, p - 2, p) % p
	flag = 1
	for i in range(mini, maxi):
		num = num * (n - i) % p
		den = den * (i + 1) % p
		if flag % 2 == 0:
			final += num * pow(den, p - 2, p) % p
		flag += 1
	return final
test = int(input())
for t in range(test):
	n = int(input())
	A = input()
	B = input()
	a = 0
	b = 0
	for i in range(n):
		if A[i] == '1':
			a += 1
		if B[i] == '1':
			b += 1
	if a + b <= n:
		high = a + b
	else:
		high = 2 * n - (a + b)
	low = abs(b - a)
	lol = ncr(n, low, high)
	print(lol % 1000000007)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = input().strip()
	b = input().strip()
	na = 0
	nb = 0
	for i in a:
		if i == '1':
			na += 1
	for i in b:
		if i == '1':
			nb += 1
	mil = abs(na - nb)
	mal = min(na, n - nb) + min(nb, n - na)
	sum = 0
	p = 1000000007
	num = den = 1
	for i in range(mil):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	ini = num * pow(den, p - 2, p) % p
	sum = ini
	for i in range(mil + 2, mal + 1, 2):
		num = num * (n - (i - 2)) % p
		den = den * (i - 1) % p
		num = num * (n - i + 1) % p
		den = den * i % p
		ini = num * pow(den, p - 2, p) % p
		sum = (sum + ini) % 1000000007
	print(sum)


N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = str(a).count('1')
	d = str(b).count('1')
	ct = 0
	if c + d >= n:
		k = n - (c + d - n)
	else:
		k = c + d
	k2 = max(c, d) - min(c, d)
	for i in range(k2, k + 1, 2):
		ct += Binomial(n, k, p) % p
		k -= 2
	print(int(ct) % p)


from math import *

def mp(n, a, b):
	n0 = 0
	n1 = 0
	for i in a:
		if i == '1':
			n1 += 1
		elif i == '0':
			n0 += 1
	for i in b:
		if i == '1':
			n1 += 1
		elif i == '0':
			n0 += 1
	return min(n, n0, n1)

def p(n, a, b):
	na1 = 0
	nb1 = 0
	for i in range(n):
		if a[i] == '1':
			na1 += 1
		if b[i] == '1':
			nb1 += 1
	return abs(na1 - nb1)

def fill(pe, f, m):
	n = len(pe) - 1
	if m % 2 == 0:
		prev = pe[0]
		i = 2
		while i <= m:
			pe[i] = prev * (n - i + 1) * (n - i + 2) // (i * (i - 1))
			prev = pe[i]
			pe[i] = pe[i] % 1000000007
			i += 2
	else:
		prev = pe[1]
		i = 3
		while i <= m:
			pe[i] = prev * (n - i + 1) * (n - i + 2) // (i * (i - 1))
			prev = pe[i]
			pe[i] = pe[i] % 1000000007
			i += 2
	return pe
t = int(input())
for i in range(t):
	n = int(input())
	a = str(input())
	b = str(input())
	max_parity = mp(n, a, b)
	parity = p(n, a, b)
	ans = 0
	series = []
	all_p = []
	if parity % 2 == 0:
		for j in range(n + 1):
			if j % 2 == 0:
				all_p.append(j)
		while parity <= max_parity:
			series.append(parity)
			parity += 2
	else:
		for j in range(n + 1):
			if j % 2 == 1:
				all_p.append(j)
		while parity <= max_parity:
			series.append(parity)
			parity += 2
	max_ans = 2 ** (n - 1) % 1000000007
	pe = [0] * (n + 1)
	pe[0] = 1
	pe[1] = n
	pe[n] = 1
	pe[n - 1] = n
	if len(series) == len(all_p):
		ans = max_ans
	else:
		pe = fill(pe, parity % 2, series[len(series) - 1])
		for k in series:
			ans = (ans + pe[k]) % 1000000007
	ans = ans % 1000000007
	print(int(ans))


fac = [1] * 1000001
Mod = 1000000007
for i in range(2, 1000001):
	fac[i] = fac[i - 1] * i % Mod

def nCr(n, r):
	return fac[n] * pow(fac[r], Mod - 2, Mod) * pow(fac[n - r], Mod - 2, Mod) % Mod
for _ in range(int(input())):
	input()
	st1 = input()
	st2 = input()
	(n1, m1) = (st1.count('1'), st2.count('1'))
	(n0, m0) = (st1.count('0'), st2.count('0'))
	min1 = abs(n1 - m1)
	max1 = min(n1, m0) + min(n0, m1) + 1
	total = 0
	for i in range(min1, max1, 2):
		total += nCr(n1 + n0, i)
	print(total % Mod)


N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
import math
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
t = int(input())
for c in range(0, t):
	y = int(input())
	x = input()
	ls = []
	y = input()
	n = len(x)
	coun = 0
	z1 = x.count('0')
	z2 = x.count('1')
	z3 = y.count('0')
	z4 = y.count('1')
	z5 = z1 + z3
	z6 = z2 + z4
	z7 = abs(z4 - z2)
	z8 = z6 % n
	if z8 == 0:
		if z6 == n:
			z8 = n
	if z6 > n:
		z9 = n - z8
	else:
		z9 = z8
	if z7 > z9:
		(z7, z9) = (z9, z7)
	coun = 0
	for u in range(z9, z7 - 1, -2):
		coun += int(Binomial(n, u, p))
	if z6 == 2 * n or z6 == 0:
		coun = 1
	print(coun % 1000000007)


for z in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	(p, q, r) = (0, 0, 0)
	for c in a:
		if c == '1':
			p += 1
	for c in b:
		if c == '1':
			q += 1
	if p > q:
		h = p
		g = q
		j = n - p
	else:
		h = q
		g = p
		j = n - q
	mn = h - g
	m = min(g, j)
	num = [0] * (n + 1)
	den = [0] * (n + 1)
	c = [0] * (n + 1)
	num[0] = den[0] = c[0] = 1
	for i in range(n):
		num[i + 1] = num[i] * (n - i) % 1000000007
		den[i + 1] = den[i] * (i + 1) % 1000000007
		c[i + 1] = num[i + 1] * pow(den[i + 1], 1000000007 - 2, 1000000007) % 1000000007
	for i in range(m + 1):
		r += c[mn]
		mn += 2
	print(r % 1000000007)