Пусть \(D(n)\) представляет собой сумму цифр числа \(n\). Для скольких целых чисел \(n\), \(10^{l} \leq n < 10^{r}\), выполняется условие \(D(k \cdot n) = k \cdot D(n)\)? Выведите ответ по модулю \(10^9+7\).
Первая строка содержит целое число \(t\) (\(1 \leq t \leq 10^4\)) — количество наборов входных данных.
Каждый набор содержит три целых числа \(l\), \(r\) и \(k\) (\(0 \leq l < r \leq 10^9\), \(1 \leq k \leq 10^9\)).
Для каждого набора входных данных выведите целое число — ответ, по модулю \(10^9 + 7\).
Для первого примера единственные значения \(n\), удовлетворяющие условию, — это \(1\) и \(2\).
Для второго примера единственные значения \(n\), удовлетворяющие условию, — это \(1\), \(10\) и \(11\).
Для третьего примера все значения \(n\) от \(10\) включительно до \(100\) исключительно удовлетворяют условию.
6 0 1 4 0 2 7 1 2 1 1 2 3 582 74663 3 0 3 1
2 3 90 12 974995667 999
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач