Divisibility

All submissions for this problem are available.
You are given m strings s_{1}, s_{2}.... s_{m} consisting entirely of digits '1', '2', '3'... '9'. You'll be given an integer d. We define subsequence of string s_{i} as f(s_{i}). We define the term mergesequence as the sequence obtained by taking the f(s_{1})f(s_{2})....f(s_{m}).You'll be given Q queries. In each query, you'll be given L,R. For each query you have to tell how many mergesequences are there, who length is L and remainder with d is R
Note that f(s_{i}) could be empty also.
Input
First line contains two integers m and d, where m is the number of strings
The next m lines contains the string s_{i}
The next line contains Q, number of queries
The next Q lines contains contains L,R as expalined in the problem.
Output
Output Q lines. For each Query, output one integer as explained in the problem. Since the output can be very large, output it MODULO 10^{9}+7.
Constraints
0 < m ≤ 10^{3}
The total length of all strings is ≤ 10^{3}
2 ≤ d ≤ 50
1 ≤ Q ≤ 10^{5}
1 ≤ L ≤ 10^{3}, 0 ≤ R ≤ d  1
Example
Input: 2 6 123 12 3 2 0 3 0 5 0 Output: 3 2 1
Explanation
3 mergesequences whose remainder with 6 is 0, and length is 2 are 12(from s_{1}),12(1 from s_{1} and 2 from s_{2}),12(from s_{3})
2 mergesequences whose remainder with 6 is 0 and length is 3 are 312(taking 3 and 12 from s_{1} and s_{2} respectively) and 132 (taking 13 and 2 from s_{1}, s_{2} respectively).
12312 is a valid mergesequence(taking 123 from s_{1} and 12 from s_{2})
Author:  bhavit_sharma 
Tags  bhavit_sharma 
Date Added:  19012017 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions