After defeating Kid Buu with the Super Spirit Bomb, Goku is called by King Kai for training.

After seeing the struggle faced by Goku in his fight against Kid Buu, in solving problems given by him to Goku, King Kai decided that it is time for Goku to learn some problem solving skills in addition to his extra-ordinary fighting skills. He believes that if Goku is able to solve such kind of problems, he will be invincible and will be able to defeat any enemy in the future, in the blink of an eye.



He has decided to give Goku some problems to solve and he will test Goku's progress by comparing his speed of answering the questions with your speed of solving the same question.

King Kai gives Goku a binary string S and an integer X. He now asks him to find the count of all the positive numbers that are less than or equal to the decimal representation of S and are also divisible by X, modulo 10⁹+7.

Solve this question quickly so that King Kai can assess the progress of Goku.

Input :

First line contains the binary string, S.
Second line contains an integer Q, denoting the number of questions.
The next Q lines each contain an integer X, as described above.

Output :

For each of the Q questions, output the answer to the problem in a separate line. Since the answer may be large, print it modulo 10⁹+7.

Constraints :

1 ≤ |S| ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ X ≤ 500