Pizza Tossing

All submissions for this problem are available.
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 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.5, 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, 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. 