EduBrick

I. Интересные числа

1000 мс · 256 МБ · всё или ничего

Число называется интересным, если его цифры идут в неубывающем порядке: 123, 1111, 888999. Посчитайте количество интересных чисел в диапазоне от LL до RR включительно по модулю 109+710^9 + 7.

Границы доходят до 1010010^{100}, так что перебор исключён — считать надо по разрядам.

Формат ввода

В первой строке число LL, во второй — число RR (1≤L≤R≤101001 \le L \le R \le 10^{100}), записанные без ведущих нулей.

Формат вывода

Выведите количество интересных чисел в диапазоне по модулю 109+710^9 + 7.

Примеры

ввод
1
100
вывод
54
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.