Chef's loves his dog so much! Once his dog created two strings a and b each of length n consisting of digits 1 and 2, and even a problem about them!
Chef's Dog will tell by barking if a string x (also containing only digits 1 and 2 and with length N) is good or not by performing the following actions.

- It starts at first digit of the string, i.e. at i = 1. 
- It can move from digit i to either i - 1 or i + 1 if xi equals 1 and the corresponding digits exist. 
- It can move from digit i to either i - 2 or i + 2 if xi equals 2 and the corresponding digits exist. 
- It must visit each digit exactly once. 
- It must finish at the last digit (XN). 

Chef's dog wants to make both the strings a and b good by choosing some subset S (possibly empty) of indices of set {1, 2, ..., n} and swapping each index i ϵ S between string a and b, i.e. swapping ai and bi. Can you find how many such subsets S exist out there? As the answer could be large, output it modulo 109 + 7.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line contains string a.
The second line contains string b.

-----Output-----
For each test case, output a single line containing answer of the problem.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ |a| = |b| ≤ 105
- '1' ≤ ai, bi ≤ '2'

-----Subtasks-----
- Subtask #1 (30 points) |a|, |b| ≤  10
- Subtask #2 (70 points) original constraints

-----Example-----
Input:
2
1111
2211
222
111

Output:
8
0

-----Explanation-----
Test case 1.
Possible subsets are: 
{}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}, {3}, {4}, {3, 4}.

Test case 2. There are no possible sets S which can make both the strings good.

Difficulty: HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc
Skill types: Dynamic programming

Starter code:

Solutions:
def fun(a):
	n = len(a)
	i = 0
	b = []
	while i < n:
		c = 0
		while i < n - 1 and a[i] == a[i + 1]:
			c += 1
			i += 1
		b.append([a[i], c + 1])
		i += 1
	return b

def tatti(h):
	n = len(h)
	i = 0
	b = []
	while i < n:
		c = 0
		while i < n - 1 and h[i][0] == h[i + 1][0]:
			c += 1
			i += 1
		b.append([h[i][0], h[i][1], c + 1])
		i += 1
	return b

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

def rem(s):
	s = list(s)
	l = len(s)
	i = l - 1
	ans = []
	c = 0
	while i >= 0:
		if s[i] == 1 and s[i - 1] == 2 and (s[i - 2] == 1) and (i >= 2):
			i -= 3
			c += 1
		else:
			i -= 1
			ans.append(c)
			c = 0
	ans.append(c)
	count = 0
	flag = 0
	for i in range(len(ans)):
		if ans[i] != 0:
			count += 1
		flag = max(flag, ans[i])
	return (count, flag)
for _ in range(int(input())):
	md = 10 ** 9 + 7
	s1 = input()
	s2 = input()
	x = []
	l = len(s1)
	for i in range(l):
		if s1[i] == '2' and s2[i] == '2':
			x.append(2)
		elif s1[i] == '1' and s2[i] == '1':
			x.append(0)
		else:
			x.append(1)
	if l == 1:
		ans = 2
	elif l == 2:
		if s1[0] == '2' or s2[0] == '2':
			ans = 0
		else:
			ans = 4
	else:
		x.pop()
		x.pop()
		h = fun(x)
		for i in range(1, len(h) - 1):
			if h[i][0] == 2 and h[i][1] == 1:
				if h[i - 1][0] == 1 and h[i + 1][0] == 1:
					h[i - 1][1] -= 1
					h[i + 1][1] -= 1
					h[i][0] = -1
		hn = []
		for i in range(len(h)):
			if h[i][1] != 0:
				hn.append(h[i])
		hnn = tatti(hn)
		flag = 0
		ans = 1
		for i in range(len(hnn)):
			if hnn[i][0] == 0:
				ans = ans * mod(2, hnn[i][1], md) % md
			elif hnn[i][0] == 1:
				if hnn[i][1] % 2 == 0:
					ans *= 2
					ans = ans % md
				else:
					ans *= 0
			elif hnn[i][0] == 2:
				if hnn[i][1] == 2:
					if i - 1 >= 0 and hnn[i - 1][0] != 0 or (i + 1 < len(hnn) and hnn[i + 1][0] != 0):
						ans *= 0
					else:
						ans *= 4
						ans = ans % md
				else:
					ans *= 0
			elif (i - 1 >= 0 and hnn[i - 1][0] == 1) and (i + 1 <= len(hnn) - 1 and hnn[i + 1][0] == 1):
				if hnn[i][2] - 1 >= 0:
					ans = ans * mod(2, hnn[i][2] - 1, md)
					ans = ans % md
			elif i - 1 >= 0 and hnn[i - 1][0] == 1 or (i + 1 <= len(hnn) - 1 and hnn[i + 1][0] == 1):
				ans = ans * mod(2, hnn[i][2], md)
				ans = ans % md
			else:
				ans = ans * mod(2, hnn[i][2] + 1, md)
				ans = ans % md
		if s1[l - 2] == '2' or s2[l - 2] == '2':
			ans *= 0
		else:
			ans *= 4
			ans = ans % md
	print(ans % md)


mod = 10 ** 9 + 7
from collections import Counter

def solve(a, b):
	n = len(a)
	if n == 1:
		return 2
	dp = Counter([('11', '11')])
	for i in range(n - 1):
		new = Counter()
		for p in ('11', '12', '21', '22'):
			for q in ('11', '12', '21', '22'):
				for (x, y) in ((a[i], b[i]), (b[i], a[i])):
					if x == '2' and p == '22' or (y == '2' and q == '22'):
						continue
					if x == '1' and p == '12' or (y == '1' and q == '12'):
						continue
					m = p[-1] + x
					n = q[-1] + y
					new[m, n] += dp[p, q]
					new[m, n] %= mod
		dp = new
	ans = 0
	for i in ('11', '21'):
		for j in ('11', '21'):
			ans += dp[i, j]
	return ans * 2 % mod
t = int(input())
for _ in range(t):
	a = input()
	b = input()
	print(solve(a, b))


T = int(input())
for t in range(T):
	S1 = list(input())
	S2 = list(input())
	N = len(S1)
	MOD = 1000000007
	count = 1
	for n in range(N - 1):
		if S2[n] == '2':
			(S1[n], S2[n]) = (S2[n], S1[n])
		if S1[n] == S2[n]:
			count = count * 2 % MOD
	count = count * 2 % MOD
	l22 = list('22')
	l11 = list('11')
	l221 = list('221')
	l222 = list('222')
	l121 = list('121')
	n = 0
	expected = [1, 2, 3, 4]
	got = 0
	while n < N - 2:
		inc = 1
		if 1 in expected and S1[n:n + 2] == l22 and (S2[n:n + 2] == l11):
			expected = [1, 2, 4]
			inc = 2
		elif 2 in expected and S1[n] == '1' and (S2[n] == '1'):
			if len(expected) < 4:
				count = count * 2 % MOD
			expected = [1, 2, 3, 4]
			inc = 1
		elif 3 in expected and S1[n:n + 3] == l221 and (S2[n:n + 3] == l221):
			expected = [1, 2, 3, 4]
			inc = 3
		elif 4 in expected and S1[n:n + 3] == l222 and (S2[n:n + 3] == l121):
			expected = [1, 2, 4]
			inc = 3
		else:
			count = 0
			break
		n += inc
	if N > 1 and (not (S1[N - 2] == '1' and S2[N - 2] == '1')):
		count = 0
	elif len(expected) < 4:
		count = count * 2 % MOD
	print(count)


import sys
import numpy as np
trans = {(11, 2): 11, (11, 3): 12, (11, 4): 22, (12, 2): None, (12, 3): 13, (12, 4): 23, (13, 2): 11, (13, 3): 12, (13, 4): None, (22, 2): None, (22, 3): None, (22, 4): 33, (23, 2): None, (23, 3): 13, (23, 4): None, (33, 2): 11, (33, 3): None, (33, 4): None}

def mpow(x, k, m):
	ret = 1
	x
	while k > 0:
		if k % 2 == 1:
			ret = ret * x % m
		x = x * x % m
		k = k // 2
	return ret

def solve(a, b):
	n = len(a)
	if n == 1:
		return 2
	if a[-2] == 2 or b[-2] == 2:
		return 0
	a[-1] = 1
	b[-1] = 1
	c = np.array(a) + np.array(b)
	ret = 0
	state = 11
	for x in c:
		if x == 2 or x == 4:
			ret += 1
		if state == 11 and x == 3:
			ret += 1
		state = trans[state, x]
		if state is None:
			return 0
	return mpow(2, ret, 10 ** 9 + 7)
f = sys.stdin
t = int(f.readline())
for i in range(t):
	a = list(map(int, list(f.readline())[:-1]))
	b = list(map(int, list(f.readline())[:-1]))
	print(solve(a, b))


modulo = 1000000007

def pow(a, n):
	res = 1
	while n > 0:
		if n & 1:
			res *= a
			res %= modulo
		a *= a
		a %= modulo
		n //= 2
	return res

def test2(s):
	if '4' in s:
		return True
	if len(s) & 1 > 0:
		return True
	return False

def test(s):
	sss = s.split('343')
	return any(map(test2, sss))
T = int(input())
for t in range(T):
	s1 = input()
	s2 = input()
	ss = ''.join(map(lambda x, y: str(int(x) + int(y)), s1, s2))
	if len(ss) > 0:
		ss = ss[:-1] + '2'
	if '444' in ss or '344' in ss or '443' in ss or (len(ss) > 1 and ss[-2] != '2'):
		print(0)
	else:
		twos = list(filter(lambda x: x and x != '44', ss.split('2')))
		if any(map(test, twos)):
			print(0)
		else:
			ones = sum(map(lambda x: x != '3', ss))
			print(pow(2, ones + len(twos)))


MOD = 1000000007
for i in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	if n == 1:
		print(2)
	elif a[n - 2] == '2' or b[n - 2] == '2':
		print(0)
	else:
		(fr, sc) = (0, 0)
		ans = 1
		for j in range(n - 1):
			c = int(a[j]) + int(b[j])
			if c == 2:
				if fr % 2 == 0 and sc % 2 == 0:
					ans = ans * 2 % MOD
					(fr, sc) = (0, 0)
				else:
					ans = 0
			elif c == 3:
				if fr == 0 and sc == 0:
					fr = 1
					ans = ans * 2 % MOD
				elif fr == 1 and sc == 0:
					fr = 2
				elif fr == 2 and sc == 0:
					sc = 1
					fr = 0
				elif fr == 0 and sc == 1:
					sc = 2
				elif fr == 0 and sc == 2:
					fr = 1
					sc = 0
				elif fr == 1 and sc == 1:
					ans = 0
				elif fr == 2 and sc == 1:
					fr = 0
					sc = 2
				elif fr == 1 and sc == 2:
					fr = 2
					sc = 0
				elif fr == 2 and sc == 2:
					ans = 0
			elif c == 4:
				if fr == 0 and sc == 0:
					fr = 1
					sc = 1
					ans = ans * 2 % MOD
				elif fr == 1 and sc == 0:
					fr = 2
					sc = 1
					ans = ans * 2 % MOD
				elif fr == 2 and sc == 0:
					ans = 0
				elif fr == 0 and sc == 1:
					sc = 2
					fr = 1
					ans = ans * 2 % MOD
				elif fr == 0 and sc == 2:
					ans = 0
				elif fr == 1 and sc == 1:
					fr = 2
					sc = 2
					ans = ans * 2 % MOD
				elif fr == 2 and sc == 1:
					ans = 0
				elif fr == 1 and sc == 2:
					ans = 0
				elif fr == 2 and sc == 2:
					ans = 0
			if ans == 0:
				break
		ans = ans * 2 % MOD
		print(ans)


size = 100000
modval = 1000000007

def main():
	t = int(input())
	for _ in range(t):
		a = input()
		b = input()
		l = len(a)
		count = 0
		if l == 1:
			count = 2
		elif l < 4:
			if checkGood(a, b, l) == 1:
				if l == 2:
					count = 4
				else:
					count = 8
		elif a[l - 2] == '2' or b[l - 2] == '2':
			count = 0
		elif parityCheck(a, b, l) == 0 and columnCheck(a, b, l) == 1:
			i = 0
			check = 1
			count = 1
			while i < l - 2:
				while i < l - 2 and a[i] == '1' and (b[i] == '1'):
					i += 1
				check = 1
				if a[i] != b[i]:
					if i < 2 or countTwo(a, b, i - 1) == 0:
						count *= 2
						if count >= modval:
							count = count % modval
					t1 = countTwo(a, b, i + 1)
					t2 = countTwo(a, b, i + 2)
					if t1 == 0:
						check = 0
					elif t1 == 1:
						i += 2
					elif t2 == 1:
						i += 3
					else:
						check = 0
				elif i < l - 2 and a[i] == '2' and (b[i] == '2'):
					if i < l - 3 and countTwo(a, b, i + 1) == 2 and (countTwo(a, b, i + 2) == 0):
						i += 3
					else:
						check = 0
				if check == 0:
					count = 0
					break
			if check == 1:
				count *= 2
				if count >= modval:
					count = count % modval
				for i in range(l - 1):
					if a[i] == b[i]:
						count *= 2
						if count >= modval:
							count = count % modval
		print(count)

def checkGood(a, b, l):
	for i in range(l - 1):
		if a[i] == '2' or b[i] == '2':
			return 0
	return 1

def parityCheck(a, b, l):
	count = 0
	for i in range(l - 2):
		if a[i] != b[i]:
			count += 1
	return count % 2

def columnCheck(a, b, l):
	if countTwo(a, b, 0) > countTwo(a, b, 1):
		return 0
	for i in range(l - 2):
		if countTwo(a, b, i) > countTwo(a, b, i - 1) + countTwo(a, b, i + 1):
			return 0
	return 1

def countTwo(a, b, i):
	count = 0
	if a[i] == '2':
		count += 1
	if b[i] == '2':
		count += 1
	return count
main()


t = int(input())
x = 1000000007
i = 0
flag = 1
(count1, count2) = (0, 0)
val = 1
while t:
	t -= 1
	a = input()
	b = input()
	n = len(a)
	if n == 1:
		print('2')
	if n >= 2:
		if a[n - 2] == '2' or b[n - 2] == '2':
			print('0')
		else:
			i = 0
			while i <= n - 2:
				if count1 == 0 and count2 == 0:
					if a[i] == b[i]:
						if a[i] == '2':
							if a[i + 1] == '2' and a[i + 2] == '1' and (b[i + 1] == '2') and (b[i + 2] == '1'):
								val = 8 * val % x
								i = i + 2
							else:
								print('0')
								flag = 0
								break
						elif a[i] == '1':
							val = 2 * val % x
					elif a[i] == '1' and b[i] == '2':
						count2 += 1
						val = 2 * val % x
					elif a[i] == '2' and b[i] == '1':
						count1 += 1
						val = 2 * val % x
				elif count1 == 0 and count2 == 1:
					if a[i] == '1' and b[i] == '1':
						print('0')
						flag = 0
						break
					elif b[i] == '2' and a[i] == '2':
						count2 += 1
						count1 += 1
						val = 2 * val % x
					else:
						count2 += 1
				elif count1 == 0 and count2 == 2:
					if a[i] == '1' and b[i] == '1':
						val = 2 * val % x
						count2 = 0
					elif a[i] == '2' and b[i] == '2':
						print('0')
						flag = 0
						break
					else:
						count2 = 0
						count1 += 1
				elif count1 == 1 and count2 == 0:
					if a[i] == '1' and b[i] == '1':
						print('0')
						flag = 0
						break
					elif a[i] == '2' and b[i] == '2':
						count2 += 1
						count1 += 1
						val = 2 * val % x
					else:
						count1 += 1
				elif count1 == 1 and count2 == 2:
					if a[i] == b[i]:
						print('0')
						flag = 0
						break
					else:
						count1 += 1
						count2 = 0
				elif count1 == 2 and count2 == 0:
					if a[i] == '1' and b[i] == '1':
						val = 2 * val % x
						count1 = 0
					elif a[i] == '2' and b[i] == '2':
						print('0')
						flag = 0
						break
					else:
						count1 = 0
						count2 += 1
				elif count1 == 2 and count2 == 1:
					if a[i] == b[i]:
						print('0')
						flag = 0
						break
					else:
						count2 += 1
						count1 = 0
				elif count1 == 2 and count2 == 2:
					if a[i] == b[i] and a[i] == '1':
						val = 2 * val % x
						count1 = 0
						count2 = 0
					else:
						print('0')
						flag = 0
						break
				i += 1
			if flag != 0:
				print(val * 2 % x)
			val = 1
			count1 = 0
			count2 = 0
			flag = 1