The Lastdigit Permeability

All submissions for this problem are available.
Penny knows that in order to continue her relationship with Leonard she should know some basic science. This makes her ask Sheldon to teach her some basic concepts of algebra Sheldon starts by teaching how different ways of parenthesizing an equation can change the result. In order to check whether Penny understood the concept he gave her a question. In the question he gave her an expression with only '+' and '*' operators without any parenthesize. And asked her in how many ways can you parenthesize it such that the last digit of the result is 'K'. As Penny and Sheldon both were not sure of the answer so they want your help to find the number of ways in which you can parenthesize an expression with only '+' and '*' operators such that the last digit of the result is 'K'.
Input
First line contains the of test cases 'T'.
Then 'T' lines follow each containing an expression and the integer 'K'.
Output
'T' lines corresponding to each test case which contain the number of ways in which you can parenthisize an expression such that the last digit of the result is 'K' MODULO 1000000009
Limits
T <= 10
length of the expression will not have more than 50 operators.
0 <= 'K' <= 9
Example
Input: 2 5+5*5+5 5 5*5+5*5 0 Output: 4 5
Test case explanation
For first test case ways of parenthesize are
(5+(5*5))+5
5+((5*5)+5)
((5+5)*5)+5
5+(5*(5+5))
Author:  udayrocks2k8 
Tags  udayrocks2k8 
Date Added:  15102011 
Time Limit:  1.03901 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. 