An m-Beautiful Number 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$
, and you have 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$
($1 ≤ T ≤ 10^5$
), number of test cases to follow. Next $T$
lines will contain $3$
integers $L$
, $R$
($1 ≤ L ≤ R ≤ 10^{50}$
), and $m$
($1 ≤ m ≤ 50$
) each as stated in description.
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 4-Beautiful Numbers between |