Given a bit-string $$str$$ of $$0s$$ and $$1s$$. you need to answer the following $$q$$ queries.
Each query will contain an integer value $$n$$. You are required to calculate how many bit-strings smaller than or equal to $$str$$ are there which are divisible by $$n$$ when converted to their decimal representation.
First line of input contains a single integer $$N$$ representing the length of string.
First line of the input contains a bit-string $$str$$ .
Second line contains a single integer $$q$$, representing the number of queries.
Next $$q$$ lines contain an integer $$n$$ .
For each of the query output the number of bit-strings smaller than or equal to $$str$$ which are divisible by $$n$$ . As the answer can be large take modulo with $$10^9+7$$.
$$1 \le N \le 10^4$$
$$ 1 \le q \le 10^5 $$
$$ 1 \le n \le 10^2 $$
For first query n is 3. Bit-strings divisible by 3 are 1100,1001,0110,0011,0000 .