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