All submissions for this problem are available.
You are given m strings s1, s2.... sm consisting entirely of digits '1', '2', '3'... '9'. You'll be given an integer d. We define subsequence of string si as f(si). We define the term merge-sequence as the sequence obtained by taking the f(s1)f(s2)....f(sm).You'll be given Q queries. In each query, you'll be given L,R. For each query you have to tell how many merge-sequences are there, who length is L and remainder with d is R
Note that f(si) could be empty also.
First line contains two integers m and d, where m is the number of strings
The next m lines contains the string si
The next line contains Q, number of queries
The next Q lines contains contains L,R as expalined in the problem.
Output Q lines. For each Query, output one integer as explained in the problem. Since the output can be very large, output it MODULO 109+7.
0 < m ≤ 103
The total length of all strings is ≤ 103
2 ≤ d ≤ 50
1 ≤ Q ≤ 105
1 ≤ L ≤ 103, 0 ≤ R ≤ d - 1
Input: 2 6 123 12 3 2 0 3 0 5 0 Output: 3 2 1
3 merge-sequences whose remainder with 6 is 0, and length is 2 are 12(from s1),12(1 from s1 and 2 from s2),12(from s3)
2 merge-sequences whose remainder with 6 is 0 and length is 3 are 312(taking 3 and 12 from s1 and s2 respectively) and 132 (taking 13 and 2 from s1, s2 respectively).
12312 is a valid merge-sequence(taking 123 from s1 and 12 from s2)
|Time Limit:||1 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, CLOJ, FS|
Fetching successful submissions