Вам дано целое число \(n\). Вы должны сделать с ним \(m\) операций.
В каждой операции вы должны заменить все цифры числа \(d\) десятичной записью числа \(d + 1\). Например, число \(1912\) становится числом \(21023\) после одной операции.
Вам нужно найти длину числа \(n\) после применения \(m\) операций. Так как ответ может быть большим, выведите его по модулю \(10^9+7\).
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 2 \cdot 10^5\)) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа \(n\) (\(1 \le n \le 10^9\)) и \(m\) (\(1 \le m \le 2 \cdot 10^5\)) — начальное число и количество операций.
Для каждого набора входных данных выведите длину получившегося числа по модулю \(10^9+7\).
В первом наборе входных данных \(1912\) превращается в \(21023\) после \(1\) операции. Длина числа равна \(5\).
Во втором наборе входных данных \(5\) превращается в \(21\) после \(6\) операций. Длина числа равна \(2\).
В третьем наборе входных данных \(999\) превращается в \(101010\) после \(1\) операции. Длина числа равна \(6\).
В четвертом наборе входных данных \(88\) превращается в \(1010\) после \(2\) операций. Длина числа равна \(4\).
5 1912 1 5 6 999 1 88 2 12 100
5 2 6 4 2115
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач