Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
m-Beautiful Numbers is a number which is divisible by m and the sum of the digits is also divisible by m. For example, 268 is a 4-Beautiful Number, but 68 and 26 are not 4-Beautiful Number.
In this problem, you’ll be given 3 integers, L, R, and m, you’ve to tell the number of m-Beautiful Numbers in between L and R inclusive . As the answer can be very large, you have to print it modulo 10^{9}+7.
The first line of the input will contain a number T, number of test cases to follow. Next T lines will contain 3 integers L, R, and m each as stated in description.
1 ≤ T ≤ 10^{5}
1 ≤ L ≤ R ≤ 10^{50}
1 ≤ m ≤ 50
For each case, you have to print the number of m-Beautiful Numbers in between L and R inclusive modulo 10^{9}+7.
Input | Output |
---|---|
2 1 20 3 1 20 4 | 6 2 |
3-Beautiful numbers between 1 to 20: 3, 6, 9, 12, 15, and 18. |
33% Solution Ratio
dip_BRUREarliest,
EgorKulikovFastest, 0.9s
dip_BRURLightest, 18 MB
mahdi.hasnatShortest, 1654B
Login to submit