Pizza Tossing

All submissions for this problem are available.
We all know that Chef has a special pizza recipe. The pizza has been a craze all over Bhiwani. The secret of the softness of the pizza lies in the fact that Chef tosses them high in the air before putting them in the oven. He makes a lot of pizzas each day to fulfill the everincreasing demand.
At some point of the time, Chef got bored. Therefore, he created a game for himself. Assume that the pizza has two sides: front side denoted by F, and back side denoted by B. He owns a lucky sequence of sides; i.e., a string of length N over alphabet {F, B}.
Chef will toss the pizza many times. After every toss, he will jot down the side that comes up. All tosses are independent and each side has equal probability of coming up (50%). He has made M tosses today. He will keep tossing until the string denoting last N tosses is equal to his lucky sequence.
Count the expected number of additional tosses Chef will make.
### Input
The first line contain a single integer T, the number of test cases. Then T description of test cases follow. Each description consists of two lines. The first line contains a single integer N followed by a string S1, separated by a space. The second line contains a single integer M followed by a string S2, separated by a space
The string S1 is the encoded form of the lucky sequence. S1 will contain only characters 'a'  'z' (that stand for values 0  25), and 'A'  'F' (that stand for values 26  31). To decode S1, concatenate the values as 5bit binary numbers of each character of S1. Then, replace 0's with F's and 1's with B's. Chef's lucky sequence is the first N characters in the resulting string.
The string S2 is the encoded form of the sequence of sides Chef has already tossed today, in the same way.
Please see the examples for more clarity.
### Output
For each test case, output a single line containing the expected number of additional tosses Chef will make. It can be proved that the answers will always be an integer. Since the answers can be very large, output each answer modulo 1,000,000,007. Note that if Chef has already achieved his lucky sequence today, he can stop right away and therefore you should output 0.
### Example Input:
```
3
1 a
0 a
3 a
2 a
8 An
3 B
```
### Example Output:
```
2
8
254
```
### Explanation:
In the third case, for the lucky sequence, 'A' stands for 26 and its 5bit binary number is 11010. 'n' stands for 13 and its 5bit binary number is 01101. Concatenate them to get 1101001101. The decoded string will be BBFBFFBBFB. Chef's lucky sequence is the first eight characters, i.e., BBFBFFBB.
### Constraints:
 1 ≤ S1, S2 ≤ 200,000
 1 ≤ N ≤ 5 × S1
 0 ≤ M ≤ 5 × S2
 (sum of S1 for all S1) ≤ 1,000,000
 (sum of S2 for all S2) ≤ 1,000,000
 (S denotes the number of characters of S.)
Author:  yellow_agony 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/PTOSS 
Tags  cook26, kmp, mediumhard, yellow_agony 
Date Added:  9032012 
Time Limit:  0.9 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, 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. 