All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Nimxor and Bit-Strings
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

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.

$$Input:$$

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$$ .

$$Output:$$

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$$.

$$Input :$$

$$1 \le N \le 10^4$$

$$ 1 \le q \le 10^5 $$

$$ 1 \le n \le 10^2 $$

SAMPLE INPUT
4
1100
4
3
4
5
7
SAMPLE OUTPUT
5
4
3
2
Explanation

For first query n is 3. Bit-strings divisible by 3 are 1100,1001,0110,0011,0000 .

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications