Chef and Two String

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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 x_{i} equals 1 and the corresponding digits exist.
 It can move from digit i to either i  2 or i + 2 if x_{i} equals 2 and the corresponding digits exist.
 It must visit each digit exactly once.
 It must finish at the last digit (X_{N}).
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 a_{i} and b_{i}. Can you find how many such subsets S exist out there? As the answer could be large, output it modulo 10^{9} + 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 ≤ 10^{5}
 '1' ≤ a_{i}, b_{i} ≤ '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.
Author:  berezin 
Tester:  alex_2oo8 
Editorial  http://discuss.codechef.com/problems/CHEFTWOS 
Tags  berezin, dynamicprogramming, easy, oct16 
Date Added:  11062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions