AND Graph

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a huge directed graph G which has a vertex for every nonnegative integer. The edges of the graph follow a strict pattern: there is a directed edge from vertex u to vertex v if and only if both the following two conditions are satisfied:
 u < v
 (u AND v) = 0, where AND is bitwise AND which is defined below.
Now Chef got curious as to how many different paths there are in graph G from vertex s to vertex t. He has a total of T questions of the above form for you. As the exact numbers of paths may be extremely large, print the answers modulo 998244353.
Note: A bitwise AND takes two equallength binary representations and performs the logical AND operation on each pair of the corresponding bits, by multiplying them. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). For example, 3 AND 5 = (011)_{2} AND (101)_{2} = (001)_{2} = 1
Input
The first line of the input contains an integer T denoting the number of test cases.Each test case consists of two lines containing binary strings s_{2} and t_{2} that are binary representations of numbers s and t respectively.
Output
For each test case, output a single line containing one integer ― the number of different paths from s to t modulo 998244353.Constraints
 1 ≤ s_{2} = t_{2} ≤ 4 000
 1 ≤ [sum of s_{2} over all T test cases] ≤ 10 000
 s < t
 t_{2} contains no leading zeroes, while s_{2} can contain some
Example
Input: 3 01 10 01 11 001 100 Output: 1 0 2
Explanation
Example case 1: There is a direct edge from vertex 1 to vertex 2 and this is the only path between these two vertices.Example case 2: Vertex 3 contains only one incoming edge in graph G and this edge is from vertex 0, but as there are no path from vertex 1 to vertex 0, thus there are no paths to vertex 3 as well.
Example case 3: The two paths are: 1 → 2 → 4 and 1 → 4.
Author:  alex_2oo8 
Tags  alex_2oo8 
Date Added:  17062017 
Time Limit:  1.5 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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 