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'.
First line contains the of test cases 'T'.
Then 'T' lines follow each containing an expression and the integer 'K'.
'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
T <= 10
length of the expression will not have more than 50 operators.
0 <= 'K' <= 9
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
|Time Limit:||1.03901 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.