Launch Tower

All submissions for this problem are available.
"The Mars Orbiter Mission probe liftedoff from the First Launch Pad at Satish Dhawan Space Centre (Sriharikota Range SHAR), Andhra Pradesh, using a Polar Satellite Launch Vehicle (PSLV) rocket C25 at 09:08 UTC (14:38 IST) on 5 November 2013".
The secret behind this successful launch was the launch pad that ISRO used. An important part of the launch pad is the launch tower. It is the long vertical structure which supports the rocket.
ISRO now wants to build a better launch pad for their next mission. For this, ISRO has acquired a long steel bar, and the launch tower can be made by cutting a segment from the bar. As part of saving the cost, the bar they have acquired is not homogeneous.
The bar is made up of several blocks, where the i^{th} block has durability S[i], which is a number between 0 and 9. A segment is defined as any contiguous group of one or more blocks.
If they cut out a segment of the bar from i^{th} block to j^{th} block (i<=j), then the durability of the resultant segment is given by ( S[i]*10^{(ji)} + S[i+1]*10^{(ji1)} + S[i+2]*10^{(ji2)} + … + S[j] * 10^{(0)} ) % M.
In other words, if W_{(i,j)} is the base10 number formed by concatenating the digits S[i], S[i+1], S[i+2], …, S[j], then the durability of the segment (i,j) is W_{(i,j)} % M.
For technical reasons that ISRO will not disclose, the durability of the segment used for building the launch tower should be exactly L. Given S and M, find the number of ways ISRO can cut out a segment from the steel bar whose durability is L.
Input
The first line contains a string S. The i^{th} character of this string represents the durability of i^{th} segment.
The next line contains a single integer Q, denoting the number of queries.
Each of the next Q lines contain two space separated integers, denoting M and L.
Output
For each query, output the number of ways of cutting the bar on a separate line.
Constraints
 1 ≤ S ≤ 2 * 10^4
 Q ≤ 5
 0 < M < 500
 0 ≤ L < M
Example
Input: 23128765 3 7 2 9 3 15 5 Output: 9 4 5
Explanation
For M=9, L=3, the substrings whose remainder is 3 when divided by 9 are: 3, 31287, 12 and 876.
Author:  admin 
Tags  acmicpc, acmamr14, admin, dynamicprogramming, easy 
Date Added:  5102014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 