Задача №113102. Интересные числа
Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 – интересные.
Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от \(L\) до \(R\) включительно. Это число может оказаться довольно большим для больших \(L\) и \(R\), поэтому Софья хочет найти остаток от деления этого числа на \(10^9\) + 7.
Требуется написать программу, которая по заданным \(L\) и \(R\) определяет количество интересных чисел, лежащих в диапазоне от \(L\) до \(R\) включительно, и выводит остаток от деления этого числа на \(10^9\) + 7.
Входной файл содержит две строки. Первая строка содержит число \(L\), вторая строка содержит число \(R\) (\(1 \le L \le R \le 10^{100}\)).
Выходной файл должен одно целое число – остаток от деления количества интересных чисел, лежащих в диапазоне от \(L\) до \(R\) включительно, на \(10^9\) + 7.
\(L = 1, R \le 1000\) Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.
\(1 \le L \le R \le 10^{18}\)
В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
\(L = 1, R = 10^k\) для некоторого целого \(k\), \(2 \le k \le 100\).
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
\(1 \le L \le R \le 10^{100}\)
В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
1 100
54