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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "mod = 10 ** 9 + 7\nfrom collections import Counter\ndef solve(a,b):\n n = len(a)\n if n == 1:\n  return 2\n dp = Counter([('11', '11')])\n for i in range(n-1):\n  new = Counter()\n  for p in '11', '12', '21', '22':\n   for q in '11', '12', '21', '22':\n    for x,y in (a[i], b[i]), (b[i], a[i]):\n     if x == '2' and p == '22' or (y == '2' and q == '22'):\n      continue\n     if x == '1' and p == '12' or (y == '1' and q == '12'):\n      continue\n     m = p[-1] + x \n     n = q[-1] + y \n     new[m,n] += dp[p,q]\n     new[m,n] %= mod\n  dp = new\n ans = 0 \n for i in '11', '21', :\n  for j in '11', '21':\n   ans += dp[i,j]\n return (ans * 2) % mod\n\n \nt = int(input())\nfor _ in range(t):\n a = input()\n b = input()\n print(solve(a,b))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13953