Codeforces Round 952 (Div. 4) |
---|
Finished |
Let D(n) represent the sum of digits of n. For how many integers n where 10l≤n<10r satisfy D(k⋅n)=k⋅D(n)? Output the answer modulo 109+7.
The first line contains an integer t (1≤t≤104) – the number of test cases.
Each test case contains three integers l, r, and k (0≤l<r≤109, 1≤k≤109).
For each test case, output an integer, the answer, modulo 109+7.
60 1 40 2 71 2 11 2 3582 74663 30 3 1
2 3 90 12 974995667 999
For the first test case, the only values of n that satisfy the condition are 1 and 2.
For the second test case, the only values of n that satisfy the condition are 1, 10, and 11.
For the third test case, all values of n between 10 inclusive and 100 exclusive satisfy the condition.
Name |
---|